Parity-check matrix - Citizendia

In coding theory, a parity-check matrix of a linear block code C is a generator matrix of the dual code. Coding theory is one of the most important and direct applications of Information theory. In Mathematics and Information theory, a linear code is an important type of Block code used in Error correction and detection schemes In Coding theory, a generator matrix is a basis for a Linear code, generating all its possible codewords In Coding theory, the dual code of a Linear code C\subset\mathbb{F}_q^n is the linear code defined by C^\perp As such, a codeword c is in C if and only if the matrix-vector product H^Tc=0. ↔

The rows of a parity check matrix are parity checks on the codewords of a code. In Mathematics, Computer science, Telecommunication, and Information theory, error detection and correction has great practical importance in In Telecommunication, a code word is an element of a Code. Each code word is a Sequence of symbols assembled in accordance with the specific rules of That is, they show how linear combinations of certain digits of each codeword equal zero. For example, the parity check matrix

$H = \begin{bmatrix} 0011\\ 1100 \end{bmatrix}$

specifies that for each codeword, digits 1 and 2 should sum to zero and digits 3 and 4 should sum to zero.

For more information see Hamming code and generator matrix. In Telecommunication, a Hamming code is a linear Error-correcting code named after its inventor Richard Hamming. In Coding theory, a generator matrix is a basis for a Linear code, generating all its possible codewords

Creating a parity check matrix

The parity check matrix for a given code can be derived from its generator matrix (and vice-versa). In Coding theory, a generator matrix is a basis for a Linear code, generating all its possible codewords If the generator matrix for an [n,k]-code in standard form is

$G = \begin{bmatrix} I_k | P \end{bmatrix}$

the parity check matrix can be calculated as

$H = \begin{bmatrix} -P^T | I_{n-k} \end{bmatrix}$

Negation is performed in the finite field mod $q$ . Note that this means in binary codes negation is unnecessary as -1 = 1 (mod 2).

For example, if a binary code has the generator matrix

$G = \begin{bmatrix} 10|101 \\ 01|110 \\ \end{bmatrix}$

The parity check matrix becomes

$H = \begin{bmatrix} 11|100 \\ 01|010 \\ 10|001 \\ \end{bmatrix}$

For any valid codeword $x$ , $H x = 0$ . For any invalid codeword $\tilde{x}$ , the syndrome $S$ satisfies $H\tilde{x} = S$ . In Communication theory and Coding theory, decoding is the process of translating received messages into Codewords of a given Code.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |