MATM FINALS: CODING THEORY AND MODULAR ARITHMETIC

Question 1

____________-is the study of the properties ofcodesand their respective fitness for specific applications. Codes are used fordata compression,cryptography,error detection and correction,data transmissionanddata storage.

Answer 1

Coding theory

Question 2

__________ are studied by various scientific disciplines, such asinformation theory,electrical engineering,mathematics,linguistics, andcomputer science—for the purpose of designing efficient and reliabledata transmissionmethods.

This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

Answer 2

Codes

Question 3

PROCESS OF CODING

Answer 3

SENDER > SOURCE ENCODER > COMMUNICATION CHANNEL > SOURCE DECODER > RECEIVER

Question 4

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).

Answer 4

Communication Channel

Question 5

It alters the message in the channel that will cause disruption and error in the messages.

Answer 5

Noises

Question 6

In transmitting messages, coding is defined as source coding and channel coding.

Answer 6

Source Coding and Channel Coding

Question 7

Two Processes in Coding
__________ - is transforming messaged into bits of message that is Suitable in communication.

___________ - is the opposite process of encoding.

Answer 7

Encoding

Decoding

Question 8

is defined as converting the message from the sender into bits suitable to the communication channel.

Answer 8

DATA COMPRESSION OR SOURCE ENCODING

Question 9

_______________- 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 int the message to a byte of 8 bits.

Answer 9

bit(short for “binary digit”)

Question 10

a____- is a unit of data that is eight binary digits long.

is the unit most computers use to represent a character such as a letter, number or typographic symbol.

Answer 10

byte

Question 11

With this problem at hand, additional process of encoding is required known as _______________

Is defined as adding some form of redundancy to the source encoded message so that the errors can be detected or even corrected.

Answer 11

Channel Coding.

Question 12

is also called as “Vertical Redundancy Check (VRC)”

Where in single bit is added to the message as redundancy bit.

The goal in doing parity check is to end up with an even parity.

A bit string is said to have an________ if there is an odd number of 1s.

Even parity if there is an even number of 1s. We add redundancy bit to message such that it will become an ___________.

Answer 12

Parity Check

odd parity

even parity

Question 13

“Perform the channel encoding by adding a redundancy bit of size 3.”

Answer 13

it is where you repeat the very last number to the given redundancy bit + while making sure it’s even

Question 14

In coding theory, therepetition codeis one of the most basic error-correctingcodes.

In order to transmit a message over a noisy channel that may corrupt the transmission in a few places, the idea of therepetition codeis 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.

formula: 2r + 1 <— this is what you’ll use to get how many times you’ll repeat the message (input r value)

“source encoded message”
“k” is how many you’ll divide it in

(final answer is the 110110110110)

Answer 14

Repetition Code: ENCODING

Question 15

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
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

do it like:
1st 2nd 3rd
1s:
0s:
then count how many

Answer 15

Repetition Code: DECODING

Question 16

Also called as Clock Arithmetic.
Is a system of arithmetic forintegers, which considers theremainder .
In modular arithmetic, numbers “wrap around” upon reaching a given fixed quantity (this given quantity is known as the modulus) to leave a remainder.

Answer 16

MODULAR ARITHMETIC

Question 17

Let a and b are integers and n is a natural counting number.

formula: a≡b(modn)
(a is congruent to b modulo n)

If the difference of a and b is divisible by n.
In addition, if n >0, and r is the remainder when b is divided by n, the integer r is referred to as the least residue.

EXAMPLE: 12≡36(mod 4)
To verify: 36-12=24 and 24 is divisible by 4

1st: subtract 36 to 12 = 24
2nd: 24 divided by 4 (mod 4)
3rd: identify if congruent or not

• it’s congruent if it isn’t decimal

Therefore, the expression is a congruence.

Answer 17

CONGRUENCE

Question 18

To determine the least residue is to simply get the remainder when b is divided by m.

b(mod m) means b divided by m.

m is referred to as the modulus (divisor)

Finding the least Residue
1. Determine the least residue of 89 (mod 9)
89/9 = Quotient of 9 and remainder of 8
Therefore, 89 (mod 9) =8

2. Determine the least residue of 120 (mod 10)
   120 is exactly divisible by 10.
   Therefore, 120 (mod 10) = 0

Answer 18

LEAST RESIDUE

Question 19

A) Modulo addition is defined (a+b)mod n
B) Modulo subtraction is defined as (a-b) mod n
C) Modulo multiplication is defined as (a*b) mod n
D) Modulo division is defined as (a/b) mod n

– + – (mod –)

Answer 19

OPERATIONS IN MODULAR ARITHMETIC