JOSH :)
1/12/22
MATM FINALS
CODES AND CRYPTOGRAPHY
Odd Parity
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
Even Parity
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
PRACTICE
I. Complete the following table by writing the channel encoded message by using parity check of
adding 1 bit in the message.
MESSAGE SOURCE ENCODING CHANNEL ENCODING (EVEN
PARITY)
ALLY 000 0000
ENEMY 011 0110
ATTACK 100 1001
RETREAT 110 1100
SURRENDER 101 1010
NOTE: If no specific parity check is given, it is automatically an “EVEN PARITY CHECK”
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 110 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 110110110110110
Repetition Code: DECODING
Example: Assume that the message transmitted through a noisy channel and distorted. The received
message is 111001101110010 .The channel encoding uses repetition code where k= 3. Decode the
received message.
Solution: 111 001 101 110 010
First Bit - Consider the most frequent bit in positions 1, 4, 7, 10, and 13
Second Bit – Consider the most frequent bit in positions 2, 5, 8, 11, and 14
pg. 1
JOSH :)
1/12/22
MATM FINALS
Third Bit – Consider the most frequents bit in positions 3, 6, 9, 12, and 15
111/001/101/110/010
1 2 3 / 4 5 6/7 8 9 /10 11 12 /13 14 15
Decoded Message: 111 – MOST REPEATED NUMBERS EVERY BITS
101
010
101
110
101
000
101
111
101
Encode the following messages using the given message and the value of r.
Source Encoding r Channel Encoding
101 2 101101101101101
100 3 100100100100100100100
001 2 001001001001001
Solution:
1. 2(2) + 1 = 5, k=5
2. 2(3) + 1 = 7, k=7
3. 2(2) + 1 = 5, k=5
MODULAR ARITHMETIC
CONGRUENCE
Example: Verify if the congruence is true
pg. 2
JOSH :)
1/12/22
MATM FINALS
a. 4 ≡ 9(mod 2) – False, since 9-4 = 5 is not divisible by 2
b. 34 ≡ 15(mod 3) – False, since 34-15 = 19 is not divisible by 3
c. 54 ≡ 19(mod 5) – True, since 54-19 = 35 is divisible by 5
d. 7 ≡ 55(mod 4) – True, since 55-4 = 48 is divisible by 4
LEAST RESIDUE
mod
Find the least residue, r
r= 54(mod 7), Solution: 54/7 = 7.71 | .71*7 = 4.97 or 5, r =5
r= 89(mod 9), Solution: 89/9 = 9.88 | .88*9 = 7.92 or 8, r = 8
r= 120(mod 10), Solution: 120/10 = 12 no remainder r = 0
r= 18 (mod 20), Solution: 18/20 = 0.9 | .9*20 = 18, r =18
pg. 3
JOSH :)
1/12/22
MATM FINALS
OPERATIONS IN MODULAR ARITHMETIC
pg. 4
JOSH :)
1/12/22
MATM FINALS
CRYPTOGRAPHY
ENCRYPTION
Is the process of transforming plain text into codes form using a certain algorithm.
DECRYPTIO
Is the process of returning/converting back the coded message into plain text.
PLAIN TEXT
refers to the original text
CIPHER TEXT
refers to the coded text
KEY
refers to the strings of information that is used to reveal the encryted message into readable
form
SHIFT CIPHER (CEASAR CIPHER)
pg. 5
JOSH :)
1/12/22
MATM FINALS
NOTE: Shift 3 to the left disregard A, B, and C
NOTE: Shift 5 to the right start with V, W, X, Y, and Z
pg. 6
JOSH :)
1/12/22
MATM FINALS
“WHEN TAKING THE EXAM ABOUT THIS CERTAIN TOPIC ALWAYS READY YOUR ALPHABETS SO
THAT IT WILL BE EASY TO SHIFT”
ADSADWDWADAWDAWDWAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
ANSWER: FUBSWRJUDSKB = Encrypted word
ANSWER: GOD IS GOOD = Decrypted word
pg. 7
JOSH :)
1/12/22
MATM FINALS
NOTE: ENCRYPTED WORDS ARE THE NEW ALPHABETS AND DECRYPTED WORDS ARE THE OLD
APLHABETS
MODULO OPERATOR
1. Express the letters of the alphabet from 0-25
2. Calculate Y=(C+K)mod 26
3. Convert the number Y into a letter following the order of the letter of the alphabet
pg. 8
JOSH :)
1/12/22
MATM FINALS
C K
K=5
pg. 9
JOSH :)
1/12/22
MATM FINALS
NOTE: IF ABOVE MOD 26 SUBTRACT IT AND IF BELOW MOD 26 STAY AS IT IS
CIPHER TEXT ENCRYPTED: RRB NX KZS YT QJFWS
FINAL ANSWER!
pg. 10
JOSH :)
1/12/22
MATM FINALS
TO DECRYPT:
Express the letters of the alphabet from 0-25
Calculate C=(Y-K) mod 26
Convert the number C into a letter following the order of the letter of the alphabet
pg. 11
JOSH :)
1/12/22
MATM FINALS
NOTE: WHEN DECRYPT K=5 SHOULD BE SUBTRACTED
NOTE: IF THERE ARE NEGATIVE NUMBERS YOU SHOULD SUBTRACT IT WITH THE MODULO 26
EX. 26-4 = 22
pg. 12
JOSH :)
1/12/22
MATM FINALS
FINAL ANSWER!
EXAMPLE GIVEN:
ENCRYPT “FATIMA” Let K = 7
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
F A T I M A
5 0 19 8 12 0
5, 0, 19, 8, 12, 0
+
7, 7, 7, 7, 7, 7
= 12, 7, 26, 15, 19, 7
Y = ( 12, 7, 26, 15, 19, 7) mod 26
Y = ( 12, 7, 0, 15, 19, 7) Note: 26-26 = 0
FINAL ANSWER: M H A P T H
pg. 13
JOSH :)
1/12/22
MATM FINALS
DECRYPT Cipher text “MHAPTH” Let K = 7
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N 0 P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
M H A P T H
12 7 0 15 19 7
12, 7, 0, 15, 19, 7
-
7, 7, 7, 7, 7, 7
= 5, 0, -7, 8, 12, 0
Y = ( 5, 0, -7, 8, 12, 0) mod 26
Y = (5, 0, 19, 8, 12, 0) Note: 26-7 = 19
FINAL ANSWER: F A T I M A
CHECK CODES AND CHECK DIGITS
ISBN – 13
CHECK DIGIT: d13 = Mod 10
1. 123-456-789-333-?
1 2 3 4 5 6 7 8 9 3 3 3
1 3 1 3 1 3 1 3 1 3 1 3
1+6+3+12+15+18+7+24+9+9+3+9 = 116/10 = 11.6 or 11 remainder 6
10-6 = 4
Remainder
Modulo
2. 432-748-909-001-?
4 3 2 7 4 8 9 0 9 0 0 1
1 3 1 3 1 3 1 3 1 3 1 3
4+9+2+21+4+24+9+0+9+0+0+3 = 85/10 = 8.5 or 8 remainder 5
10-5 = 5
pg. 14
JOSH :)
1/12/22
MATM FINALS
UPC
CHECK DIGIT: d12 = Mod 10
1. 3-12345-67890-?
3 1 2 3 4 5 6 7 8 9 0
3 3 3 3 3 3
9+1+6+3+12+5+18+7+24+9+0 = 94/10 = 9.4 or 9 remainder 4
10-4 = 6
2. 4-15902-74212-?
4 1 5 9 0 2 7 4 2 1 2
3 3 3 3 3 3
12+1+15+9+0+2+21+4+6+1+6 = 77/10 = 7.7 or 7 remainder 7
10-7 = 3
CHECK DIGITS ON CREDIT CARD
CHEK DIGIT: d16 = Mod 10
1. 3212-3921-8282-123?
3 2 1 2 3 9 2 1 8 2 8 2 1 2 3
2 2 2 2 2 2 2 2
6+2+2+2+6+9+4+1+16+2+16+2+2+2+6
NOTE: “When adding it should be always a single digit number.”
6+2+2+2+6+9+4+1+1+6+2+1+6+2+2+2+6 = 60 no remainder so automatic = 1
2. 3219-1245-7542-927?
3 2 1 9 1 2 4 5 7 5 4 2 9 2 7
2 2 2 2 2 2 2 2
pg. 15
JOSH :)
1/12/22
MATM FINALS
6+2+2+9+2+2+8+5+14+5+8+2+18+2+14
6+2+2+9+2+2+8+5+1+4+5+8+2+1+8+2+1+4 = 72/10 = 7.2 or 7 remainder 2
10-2 = 8
UPS
CHECK DIGIT: d11 = Mod 9
1. Determine the check digit for USPS if the first 10 digits are 12-2133-1321.
Solution: (1+2+2+1+3+3+1+3+2+1) mod 9
19 mod 9 = 1, because 19 = 9(2) = 18 + 1
Final Answer = 1
2. 6966133421
Solution: (6+9+6+6+1+3+3+4+2+1) mod 9
41 mod 9 = 5, because 41 = 9(4) = 36 + 5
Final Answer = 5
ISBN – 10
CHECK DIGIT: d10 = Mod 11
1. 4-7382-9121-?
4 7 3 8 2 9 1 2 1
10 9 8 7 6 5 4 3 2
40+63+24+56+12+45+4+6+2 =252/11
11-10 = 1 = Manual Divide
pg. 16
JOSH :)
1/12/22
MATM FINALS
APPORTIONMENT
1. Hamilton Plan
40/9.95= 4.02 4 4
3.52 3 4
2.21 2 2
3.82 3 4
2.51 2 2
3.92 3 4
N= 17 20
(a) D = 199/20 = 9.95
(b) Q = 40/9.95 = 4.02 or 4
pg. 17
JOSH :)
1/12/22
MATM FINALS
2. Jefferson Plan
Note: Trial and Error
“The modified uses an assume value always smaller than the standard divisor.”
“This method uses a modified standard divisor that arrives at the correct or exact numbers
of representative using trial and error. “
pg. 18
JOSH :)
1/12/22
MATM FINALS
3. Apportionment Principle
pg. 19
JOSH :)
1/12/22
MATM FINALS
4. Huntington – Hill apportioned method
pg. 20
JOSH :)
1/12/22
MATM FINALS
Voting
1. MAJORITY AND PLURALITY METHOD
pg. 21
JOSH :)
1/12/22
MATM FINALS
2. BORDA COUNT METHOD
3. PLURALITY BY ELIMINATION METHOD
pg. 22
JOSH :)
1/12/22
MATM FINALS
pg. 23
JOSH :)
1/12/22
MATM FINALS
SOLUTION:
pg. 24
JOSH :)
1/12/22
MATM FINALS
4. PAIRWISE COMPARISON VOTING
pg. 25
JOSH :)
1/12/22
MATM FINALS
pg. 26
JOSH :)
1/12/22
MATM FINALS
SOLUTION:
pg. 27
