Virtual Labs

Message Passing Decoding of LDPC Codes on Other Channels

Given a generator matrix

G

for a linear block code, the corresponding parity check matrix

H

must satisfy which of the following conditions for all codewords?

GH^T = I

, where

I

is the identity matrix Explanation

Explanation

G = H^T

Explanation

GH^T = 0

, where

0

is the zero matrix Explanation

Explanation

G + H^T = 0

, where

0

is the zero matrix Explanation

Explanation

If the syndrome

s = rH^T

for a received vector

r

is non-zero, what does this imply?

r

is a valid codeword. Explanation

Explanation

r

is not a valid codeword, indicating an error has occurred. Explanation

Explanation

c: The parity check matrix

H

must be incorrect. Explanation

Explanation

d: The channel was noiseless. Explanation

Explanation

For a Binary Symmetric Channel (BSC) with crossover probability

p=0.1

, if the codeword

c = (1, 0, 1, 0)

is sent, what is the probability that the received vector is

r = (1, 1, 1, 0)

0.001

Explanation

0.081

Explanation

0.0729

Explanation

0.1

Explanation

What is the key difference in the output of a Binary Erasure Channel (BEC) compared to a Binary Symmetric Channel (BSC)?

a: A BEC can flip bits from 0 to 1, but not 1 to 0. Explanation

Explanation

b: A BEC introduces a third output symbol, 'erasure', and does not flip bits. Explanation

Explanation

c: A BEC always erases the first bit of every codeword. Explanation

Explanation

d: A BEC has a higher probability of error than a BSC. Explanation

Explanation

In a Tanner graph representation of an LDPC code, what do the two distinct sets of nodes represent?

a: Message bits and parity bits Explanation

Explanation

b: Variable nodes (codeword bits) and check nodes (parity-check equations) Explanation

Explanation

c: Input vectors and output vectors Explanation

Explanation

d: Generator matrix rows and parity check matrix columns Explanation

Explanation

What is the primary characteristic of the noise in an Additive White Gaussian Noise (AWGN) channel?

a: The noise is uniformly distributed and correlated. Explanation

Explanation

b: The noise values are statistically independent and follow a Gaussian (normal) distribution. Explanation

Explanation

c: The noise is binary and flips transmitted bits with a certain probability. Explanation

Explanation

d: The noise replaces transmitted bits with an erasure symbol. Explanation

Explanation

What is the first step in the peeling decoding algorithm for an LDPC code over a BEC?

a: Find a variable node connected to only one check node. Explanation

Explanation

b: Identify a received bit that has been flipped. Explanation

Explanation

c: Find a check node that is connected to only one erased variable node. Explanation

Explanation

d: Guess the value of the first erased bit and check the syndrome. Explanation

Explanation

A code has the parity check equation

c_1 + c_3 + c_4 = 0

. The received vector over a BEC is

r = (1, 0, e, 0)

, where 'e' is an erasure. What is the decoded value of the erased bit

c_3

a: 0 Explanation

Explanation

b: 1 Explanation

Explanation

c: Cannot be determined from this equation alone Explanation

Explanation

d: Both 0 and 1 are possible Explanation

Explanation

After the peeling decoder successfully resolves an erasure using a degree-1 check node, what is the immediate next step?

a: The algorithm terminates, as one bit has been corrected. Explanation

Explanation

b: The decoder requests a retransmission of the entire codeword. Explanation

Explanation

c: The graph is simplified by removing the now-satisfied check equation, and the process is repeated. Explanation

Explanation

d: The decoder calculates the syndrome of the partially corrected word to verify its work. Explanation

Explanation

Under which condition will the peeling decoder for a BEC get stuck and fail to decode all erasures?

a: The received vector contains an odd number of erasures. Explanation

Explanation

b: The channel's erasure probability

\epsilon

is greater than 0.5. Explanation

Explanation

c: There are no check nodes of degree 1 connected to the remaining erased bits. Explanation

Explanation

d: The generator matrix

G

is not in systematic form. Explanation

Explanation