GEMMWO1X
MATHEMATICS IN THE MODERN WORLD
MATHEMATICS AS A TOOL:
Coding Theory and Modular Arithmetic
ELDIMAR D. BACSAL, MSEd, LPT
Professor
V. Mathematics as a Tool: Coding Theory & Modular Arithmetic
5.1 5.2 5.3 Check
Coding Theory Cryptography Codes and
and Modular Digits
Arithmetic
Learning Outline
V. Mathematics as a Tool: Coding Theory & Modular Arithmetic
At the end of the chapter the students are expected:
Perform the coding of a word text using the
different method.
5.1
Decrypt the different message.
Coding Theory
and Modular
Arithmetic
Learning Outcomes
LESSON 1:
CODING THEORY
CODES AND CRYPTOGRAPHY
Coding Theory
Coding theory is the study of the properties of codes and their respective fitness for
specific applications. Codes are used for data compression, cryptography, error detection
and correction, data transmission and data storage.
Codes are studied by various scientific disciplines, such as information
theory, electrical engineering, mathematics, linguistics, and computer science — for the
purpose of designing efficient and reliable data transmission methods.
This typically involves the removal of redundancy and the correction or detection of
errors in the transmitted data.
CODES AND CRYPTOGRAPHY
Coding Theory
The communication system is composed of the sender (or message
source), the communication channel, and the receiver.
Communication Channel
✓ It is the physical medium through which information is transmitted.
✓ Ex: telephone lines, internet cables, fiber-optic lines, and air. Some
storage data can be considered channels (CD-ROMS, hard drives).
Noises
✓ It alters the message in the channel that will cause disruption and error
in the messages.
CODES AND CRYPTOGRAPHY
Coding Theory
The communication system is composed of the sender (or message
source), the communication channel, and the receiver.
Source Coding and Channel Coding
✓ In transmitting messages, coding is defined as source coding and channel
coding.
Two Processes in Coding
✓ Encoding is transforming messaged into bits of message that is suitable
in communication.
✓ Decoding is the opposite process of encoding.
CODES AND CRYPTOGRAPHY
Coding Theory
DATA COMPRESSION OR SOURCE ENCODING
is defined as converting the message from the
sender into bits suitable to the
communication channel.
- bit (short for "binary digit") is the
smallest unit of measurement used to quantify
computer data. It contains a single binary
value of 0 or 1.
An example of this is the ASCII (AMERICAN
STANDARD CODE) that converts each
character in the message to a byte of 8 bits.
CODES AND CRYPTOGRAPHY
Coding Theory
American Standard Code (ASCII Code)
EXAMPLE
In most computer
Consider the source encoding of four
systems, a byte is a unit of data
directions as follows:
that is eight binary digits long.
NORTH - 00
A byte is the unit most
SOUTH - 01
computers use to represent a
EAST - 10
character such as a letter,
WEST - 11
number or typographic symbol.
CODES AND CRYPTOGRAPHY
Coding Theory
American Standard Code (ASCII Code)
EXAMPLE Suppose the message
Consider the source encoding of four “NORTH”, which is encoded as 00, is
directions as follows: transmitted over a noisy channel.
NORTH - 00 The message may encounter
SOUTH - 01 errors and may be received as 01.
The receiver will get the message 01
EAST - 10
and decode it as “SOUTH” without
WEST - 11 realizing that the message is
corrupted.
CODES AND CRYPTOGRAPHY
Coding Theory
With this problem at hand, additional process of encoding is required
known as Channel Coding.
CODES AND CRYPTOGRAPHY
Coding Theory
Channel Coding
✓ It is defined as adding some form of redundancy to the source encoded message so
that the errors can be detected or even corrected.
Parity Check
✓ Parity check is also called “Vertical Redundancy Check (VRC)”, wherein a single bit is added
to the message as a redundancy bit.
✓ A bit string is said to have an odd parity if there is an odd number of 1s.
✓ Even parity if there is an even number of 1s.
✓ We add a redundancy bit to the message such that it will become an even parity.
CODES AND CRYPTOGRAPHY
Coding Theory
There is two types of parity bits in error detection, they are:
Even Parity bit
✓ If the data has even number of 1’s, the parity bit is 0.
✓ Odd number of 1’s, the parity bit is 1.
Ex: data is 10010001 -> parity bit 1
Odd Parity bit
✓ If the data has odd number of 1’s, the parity bit is 0.
✓ Even number of 1’s, the parity bit is 1.
Ex: data is 10010101 -> parity bit 1
CODES AND CRYPTOGRAPHY
Coding Theory
EXAMPLE Suppose again that the message
Consider the source encoding of four “north”, which is source encoded as 00
directions as follows: and again channel encoded as 000, is
transmitted over a noisy channel.
NORTH - 00
SOUTH - 01 The message may encounter
EAST - 10 errors and may be received as 001, 010,
WEST - 11 or 100. In this manner, we can detect
that there is an error in the message
since none of the three possible
We perform the channel encoding by adding a messages is among the source encoded
redundancy bit of size 1 as follows: messages.
00→000, 01→011, 10→101, 11→110.
CODES AND CRYPTOGRAPHY
Coding Theory
PERFORM THE CHANNEL ENCODING BY ADDING A
REDUNDANCY BIT OF SIZE 3.
1. 00
2. 01
3. 10
4. 11
CODES AND CRYPTOGRAPHY
Coding Theory
PERFORM THE CHANNEL ENCODING BY ADDING A
REDUNDANCY BIT OF SIZE 4.
1. 001
2. 010
3. 110
4. 011
CODES AND CRYPTOGRAPHY
Coding Theory
Repetition Code
✓ In coding theory, the repetition code is one of the most basic error-correcting codes.
✓ In order to transmit a message over a noisy channel that may corrupt the
transmission in a few places, the idea of the repetition code is to just repeat the
message several times.
✓ Suppose that the source encoding is already done and that the encoded message is of
fix length k. The channel encoding by repetition is performed by taking the k bits then
repeating it 2r + 1, where r is greater than or equal to 1 is a fixed integer.
Example
Suppose that the source encoded message is 101 where k=3. If you choose r= 2 , the
message must be repeated 2r +1 = 2(2) + 1 or 5 times.
This will result to 101101101101101
CODES AND CRYPTOGRAPHY
Coding Theory
1. Suppose that the source encoded message is 01. If
𝑟 = 2, what will be the message?
2. Suppose that the source encoded message is 001.
If 𝑟 = 4, what will be the message?
CODES AND CRYPTOGRAPHY
Coding Theory
Repetition Code The decoding process will be done in
Example this manner.
Instead of
Consider the positions 1, 4, 7,
101101101101101, 10, 13 of the received message. We
will take the most frequent bit as the
assume that the message is transmitted first decoded bit. Then, consider 2, 5,
through a noisy channel and distorted. The 8, 11, 14 positions and do the same
received message is process to get the second bit. For the
third and last bit, consider the
111101100011100. positions 3, 6, 9, 12, and 15. With this,
the decoded message will be 101.
CODES AND CRYPTOGRAPHY
Coding Theory
1. Assume noise affected the message, and the
decoded message was 000110011111101101001.
Determine the correct source encoded if 𝑘 = 3.
2. Assume noise affected the message, and the
decoded message was 100100001010010.
Determine the correct source encoded if 𝑘 = 3.
LESSON 2:
MODULAR ARITHMETIC
CODES AND CRYPTOGRAPHY
Modular Arithmetic
Modular arithmetic is a system of arithmetic
for integers, which considers the remainder. Modular
arithmetic is a way of working with numbers where
values wrap around after reaching a fixed number called
the modulus.
In simple terms, instead of numbers going on forever,
they cycle within a set range.
CODES AND CRYPTOGRAPHY
Modular Arithmetic
CONGRUENCE
Let 𝒂 and 𝒃 be integers, and 𝒏 be a natural counting
number.
We say that 𝑎 is congruent to 𝑏 modulo 𝑛, in symbols,
𝒂 ≡ 𝒃 𝐦𝐨𝐝 𝒏 , if the difference of 𝒂 and 𝒃 is divisible
by 𝒏.
EXAMPLES
I. Verify if the following congruences are true.
1. 9 ≡ 3 (mod 2) It is true since 9 – 3 = 6, which is divisible by 2.
2. 15 ≡ 4 (mod 3) It is false since 15 – 4 = 11, which is not divisible by 3.
3. 15 ≡ 7 (mod 4) It is true since 15 – 7 = 8, which is divisible by 4.
4. 5 ≡ 20 (mod 3) It is true since 5 – 20 = -15, which is divisible by 3.
5. 4 ≡ 20 (mod 3) It is false since 4 – 20 = -16, which is not divisible
by 3.
CODES AND CRYPTOGRAPHY
Modular Arithmetic
CONGRUENCE
Corollary: The integer 𝒓 is the remainder when 𝑎 is
divided by 𝑛 if and only if 𝑎 ≡ 𝑟 (mod 𝑛), where 0 ≤ 𝑟 <
𝑛.
By this corollary, every integer 𝑎 is congruent to its
remainder 𝑟 modulo 𝑛; 𝒓 is called the least residue of a
modulo 𝑛.
EXAMPLES
II. Solve the least residue of the following.
1. 29 (mod 3) Answer is 2, since 2 is the remainder of 29/3.
2. 35 (mod 4) Answer is 3, since 3 is the remainder of 35/4.
3. 50 (mod 7) Answer is 1, since 1 is the remainder of 50/7.
4. 30 (mod 4) Answer is 2, since 2 is the remainder of 30/4.
5. 25 (mod 5) Answer is 0, since there is no remainder of 25/5.
CODES AND CRYPTOGRAPHY
Modular Arithmetic
OPERATIONS IN MODULAR ARITHMETIC
Operations in Modular Arithmetic are just normal
operations, same as how we use in normal arithmetic
Consider modulo n:
A) Modular addition is defined 𝑎 + 𝑏 𝑚𝑜𝑑 𝑛
B) Modular subtraction is defined as (𝑎 − 𝑏) 𝑚𝑜𝑑 𝑛
C) Modular multiplication is defined as (𝑎 ∗ 𝑏) 𝑚𝑜𝑑 𝑛
𝑎
D) Modular division is defined as 𝑚𝑜𝑑 𝑛
𝑏
EXAMPLES
III. Solve the following modular arithmetic
1. (10 – 4) (mod 5) 1
2. (11 + 7) (mod 3) 0
3. (8 + 7) (mod 7) 1
4. (20 – 7) (mod 5) 3
5. (31 – 6) (mod 4) 1
Thank you for listening ☺