Virtual Labs

Error Detection and Correction, Standard Array, Syndrome Decoding

1. Let

G

and

H

be generator and parity check matrices of a linear block code respectively. Then the syndrome of the vector

\mathbf{w} \in \mathbb{F}_2^n

is defined as

\mathbf{w}G^T

Explanation

\mathbf{w}H^T

Explanation

H\mathbf{w}^T

Explanation

G\mathbf{w}^T

Explanation

2. Consider the linear block code generated by the following parity matrix

H

. What is the syndrome of the vector

1001011

\begin{align*} G = \begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{bmatrix} \end{align*}

a: 011 Explanation

Explanation

b: 100 Explanation

Explanation

c: 101 Explanation

Explanation

d: None of the above Explanation

Explanation

3. Let

\mathbf{e}_2

and

\mathbf{e}_5

be the coset leaders of the 2nd and 5th rows of a standard array of some linear block code respectively. Then which of the choices of

\mathbf{e}_2

and

\mathbf{e}_5

are incorrect for an optimal decoding over BSC

(p)

with

p=0.01

\mathbf{e}_2 = 0010

and

\mathbf{e}_5=0001

Explanation

\mathbf{e}_2 = 010000

and

\mathbf{e}_5=001101

Explanation

\mathbf{e}_2 = 00110

and

\mathbf{e}_5=01000

Explanation

d: All are valid. Explanation

Explanation

4. Consider

\mathbf{y}_1, \mathbf{y}_2 \in \mathbb{F}_2^n

such that

\mathbf{y}_1 = \mathbf{v}_1 + \mathbf{e}

and

\mathbf{y}_2 = \mathbf{v}_2 + \mathbf{e}

, where

\mathbf{v}_1

and

\mathbf{v}_2

are codewords and

\mathbf{e}

is an arbitrary vector in

\mathbb{F}_2^n

. Then choose the correct statement.

\mathbf{y}_1

and

\mathbf{y}_2

have the same syndrome. Explanation

Explanation

\mathbf{y}_1

and

\mathbf{y}_2

have different syndromes. Explanation

Explanation

c: Data insufficient Explanation

Explanation

d: None of the above Explanation

Explanation

5. Standard array decoding and syndrome decoding may give different decoded codewords for the same received vector. True or false?

a: True Explanation

Explanation

b: False Explanation

Explanation

6. For a

(7, 4)

linear block code, how many rows are there in the standard array?

a: 4 Explanation

Explanation

b: 7 Explanation

Explanation

c: 8 Explanation

Explanation

d: 16 Explanation

Explanation

7. In a standard array, all vectors in the same row have the same property. What is it?

a: Same Hamming weight Explanation

Explanation

b: Same syndrome Explanation

Explanation

c: Same distance from the all-zero vector Explanation

Explanation

d: All are codewords Explanation

Explanation

8. If a linear block code has

2^{10}

codewords and the standard array has 128 rows, what is the code length

n

a: 10 Explanation

Explanation

b: 17 Explanation

Explanation

c: 7 Explanation

Explanation

d: Cannot be determined Explanation

Explanation

9. For BSC

(p)

with

p < 1/2

, which vectors are chosen as coset leaders in the standard array for optimal decoding?

a: Vectors with maximum Hamming weight Explanation

Explanation

b: Vectors with minimum Hamming weight Explanation

Explanation

c: Random vectors not yet in the array Explanation

Explanation

d: Only codewords Explanation

Explanation

10. What is the main advantage of syndrome decoding over standard array decoding?

a: Better error correction capability Explanation

Explanation

b: Reduced storage requirements Explanation

Explanation

c: Faster decoding speed Explanation

Explanation

d: Can correct more errors Explanation

Explanation

11. Consider a

(15, 11)

linear block code. If the syndrome of a received vector is

\mathbf{s} = [0, 0, 0, 0]

, what can be concluded?

a: The received vector has errors Explanation

Explanation

b: The received vector is a codeword Explanation

Explanation

c: The received vector cannot be decoded Explanation

Explanation

d: Multiple errors occurred Explanation

Explanation

12. In syndrome decoding, if two different error patterns

\mathbf{e}_1

and

\mathbf{e}_2

result in the same syndrome, which one is chosen for decoding?

a: The one with larger Hamming weight Explanation

Explanation

b: The one with smaller Hamming weight Explanation

Explanation

c: Either one, as they are equivalent Explanation

Explanation

d: This situation cannot occur Explanation

Explanation

13. For a

(n, k)

linear block code with minimum distance

d_{min} = 5

, how many error patterns can be guaranteed to be corrected using standard array decoding?

a: All error patterns of weight up to 2 Explanation

Explanation

b: All error patterns of weight up to 5 Explanation

Explanation

c: Exactly

2^{n-k}

error patterns Explanation

Explanation

d: All error patterns Explanation

Explanation

14. Which statement about the standard array is FALSE?

a: Each column contains exactly one codeword Explanation

Explanation

b: The first row contains all codewords Explanation

Explanation

c: Each row has the same syndrome Explanation

Explanation

d: The standard array is unique for a given code Explanation

Explanation