Parity Check Matrix and Syndrome Testing
The parity check matrix is used to decode linear block codes with generator matrix G.
Parity Check Matrix:
- The parity check matrix H corresponding to a generator matrixG = [Ik|P]is defined as
- It is easily verified that GHT = 0k,n−k, where 0k,n−k denotes an all zero k ×(n−k) matrix
- Given codeword Ci in the code is obtained by multiplication of the information bit sequence Ui by the generator matrix G: Ci = UiG
- For any input sequence Ui, where 0n−k denotes the all-zero row vector of length n – k.Thus, multiplication of any valid codeword with the parity check matrix results in an all zero vector.
- This property is used to determine whether the received vector is a valid codeword or has been corrupted, based on the notion of syndrome testing
- Let R be the received codeword resulting from transmission of codeword C. In the absence of channel errors, R = C.
- If the transmission is corrupted, one or more of the codeword symbols in R will differ from those in C. We therefore write the received codeword as
- Where e = [e1e2 . . . en] is the error vector indicating which codeword symbols were corrupted by the channel. We define the syndrome of R as ― (4)
- If R is a valid codeword, i.e. R = Ci for some i, then S = CiHT = 0n−k by (2). Thus, the syndrome equals the all zero vector if the transmitted codeword is not corrupted, or is corrupted in a manner such that the received codeword is a valid codeword in the code that is different from the transmitted codeword
- If the received codeword R contains detectable errors, then S ≠0n−k.
- If the received codeword contains correctable errors, then the syndrome identifies the error pattern corrupting the transmitted codeword, and these errors can then be corrected.
- Note that the syndrome is a function only of the error pattern e and not the transmitted codeword C, since ― (5)
- Since S = eHT corresponds to n − k equations in n unknowns, there are 2k possible error patterns that can produce a given syndrome S
- If an error pattern ˆe is the most likely error associated with a given syndrome S, the transmitted codeword is typically decoded as ― (6)
- When the most likely error pattern does occur, i.e. ˆe = e, then ˆC = C, i.e. the corrupted codeword is correctly decoded.