L4 Codes

Question 1

What is BCD? How to convert BCD -> decimal?

Answer 1

• BCD = binary coded decimal
• Each digit in decimal number is represented as its binary equivalent.
• Break BCD representation into groups of 4 and convert back to decimal

Question 2

What is ASCII?

Answer 2

American Standard Code for Information Interchange

• 7 bit alphanumeric code for 128 different symbols
  
  • ​(sometimes represeted using 2 hex digits 0-7F)
• Fixed-length code: each symbol is coded using the same number of bits

Question 3

Example

How many ways can we map the digits 0-9 to 4 bit codewords?

Answer 3

There are 16 possible 4 bit codewords.

16*15*14*13*12*11*10*9*8*7=29059430400

Question 4

What are variable length codes?

Answer 4

• Takes into account the probabilities of the symbols
• Symbols with higher probability are assigned codes with shorter lengths, symbols with lower probability are assigned codes with higher lengths
• E.g. Huffman coding

Question 5

Example:

A source of data produces five different characters which we label a, b, c, d and e. The relative frequency of occurrence of these characters is 0.5, 0.3, 0.1, 0.05 and 0.05 respectively.

(a) Design a fixed-length code for these characters.
(b) Design a variable-length code for these characters that requires a lower average number of bits per symbol than the fixed-length code. Be careful to check that you variable length code can be decoded.

Answer 5

Character

Relative frequency

Fixed length code

Variable length code

a

0.5

000

0

b

0.3

001

10

c

0.1

010

110

d

0.05

011

1110

e

0.05

100

1111

Analysis

• Fixed length code requires 3 bits/symbol
• Variable length code requires on average 1*0.5+0.3*2+0.1*3+0.05*4*2 = 1.8 bits/symbol

Question 6

What is the purpose of error control coding? Provide and example of an error control code.

Answer 6

• When digital data is transmitted from one place to another or stored it is possible for some bits to be received or read in error
• So digital systems employ codes to detect (and even correct) such errors
• E.g. parity check code

Question 7

How does (the simplest type of) a parity check code work?

Answer 7

• Break string into chunks (groups of bits)
• Add one additional bit (called parity bit or check bit) to end of each chunk so that the total number of ones in that chunk is even.
• These added bits are called check bits or parity bits
• Allows you to detect an odd number of errors but you can’t correct them

Question 8

Which of the following bits are valid codewords:

a) 10101
b) 11101
c) 00000

Answer 8

Only b) and c) because they have even number of 1s

Question 9

Determine parity bit to be attached to the following digital data strings, given that we add 1 bit to four information bits.

a) 0110
b) 1011

Answer 9

a) 0
b) 1

Question 10

What is the minimum number of bit positions in which two codewords differ when parity check code is used?

Answer 10

2

Question 11

How do you judge a code as being better than another code?

Answer 11

Has to work

• Each symbol is uniquely decodable -> must be prefix free
  
  • Otherwise, there are some symbols that will consistently be decoded incorrectly
• Lower average bits/symbol
  
  • less overhead so more information can be sent given the same bandwidth