Information Redundancy.

Question 1

What are the requirements of a code ? 3 answers.

Answer 1

Detects all likely errors
• Achieves the desired degree of error detection using minimum redundancy
• The encoding and decoding process is fast and simple

Question 2

The kind of errors to be expected is application and technology dependent. Explain the types of errors shortly.

Answer 2

Symmetric errors: Both 0->1 and 1->0 can occur with equal probability.
Asymmetric errors: Only 0 -> 1 or 1 -> 0 occur.
Unidirectional: Both 0->1 and 1->0 can occur, but not in the same CW.
Burst errors: affects contiguous series of bits.

Question 3

What are the 3 key characteristics of a code

Answer 3

Number of errors that can be corrected
Number of errors that can be detected
Types of errors that can be corrected.

Question 4

What are the overheads of a code?

Answer 4

Redundancy required

Time to encode/decode.

Question 5

What is the main advantage of a separable code.

Answer 5

Allows to process the incoming data, while its integrity is been checked.

Question 6

Unordered codes are capable of detecting …

Answer 6

all unidirectional errors.

It is a code where any codeword is not covered by any other cw.

Question 7

The Hamming relationship determines the minimum number of parity check bits required for single‐error correction. Describe the relation between the number of check bits and code length to correct one single error.

Answer 7

The c check bits allow us to distinguish 2^c cases.

2^c >= n +1.

Question 8

What is the idea bihing a HSIAO Code

Answer 8

Use syndromes with an odd number of ones for the check matrix.
Double bit errors lead to a syndrome with an even number of 1’s and can be detected.

Question 9

Properties of a HSIAO code

Answer 9

Corrects 1 bit errors and detects 2 bit errors.
All columns of H have odd weight (optimized wrt. the number of 1s)
reduced overhear and increased encoding/decoding performance.

Question 10

Types of checksum codes

Answer 10

Single precision - sum word with same length
Double Precision - sum word has twice the length of word
Residue Checksum - same as single prec. but carry bit is added again.
Honeywell Checksum - Concatenates two words to add (overcome stuck at faults)

Question 11

M‐of‐N Codes characteristics

Answer 11

M bits out of N are 1. (N-M are 0)
Non linear
Detects all unidirectial errors
(n ) codewords
(m)
Optimal case is N = 2M

Question 12

Principle of the Berger Code

Answer 12

Count the number of 1s (or 0s) of a word and add this info to the cw.

Question 13

A linear code is a cyclic code if for any code word the rotated word is …

Answer 13

also a codeword.

Question 14

An (n,k) cyclic code can detect multiple adjacent bits errors as long as …

Answer 14

fewer than n-k bits are affected by the error.

Question 15

Properties of the generator polynomial g(x) of a cyclic code.

Answer 15

Degree r = n - k.
There exists no other non zero poly with order lower or equal to r.
Constant coefficient g0 is 1
All 2^k multiples of g(x) are codewords

Question 16

How is the decoding procedure of cyclic codes:

Answer 16

The received data is divided by g(x)… the remainder of the division should be zero.