ERROR-CORRECTING CODES

1.1 Classification of basic error-correcting codes

Currently the large number of the codes correcting errors are known, that are used for transmitting of discrete messages, and that’s why their systematization and classification are very difficult. At the construction of classification diagram (figure 1.1) examined only those codes that find most application in the data transmission systems.

Figure 1.1 – Classification of basic error-correcting codes

Binary error-correcting codes can be divided into three great classes: block, convolutional and concatenated. Block codes are codes, in which encoding and decoding are carried out within a block consisting of the specified number of code symbols. Convolutional are codes, in which encoding and decoding processes are continuous, without explicit allocation limits for the construction of the code signal. Concatenated codes use together two or more correction codes.

Block codes are divided into linear and nonlinear. Linear codes are those in which the construction of blocks, i.e. coding, is performed using linear operations over information symbols. Otherwise, the error-correcting codes are referred nonlinear. The simplest example of a nonlinear code is the international code of seven elements, which is called the code with constant weight (CCW), in which each codeword has three ones and four zeros in all possible combinations.

Linear codes are divided into systematic and nonsystematic. In systematic codes, information symbols in the output of the encoder are represented explicitly. Belonging to a systematic or nonsystematic code is determined by the choice of the code and the coding algorithm. A significant part of the linear codes occupy cyclic codes (CC), which find wide application in communication systems. The large number of correcting codes belong to CC, among that most known are: Hamming codes, BCH codes, group of codes with the majority-logical decoding (MLD), Fire codes.

Convolutional codes (CvC) also can be divided into systematic and nonsystematic. The first (systematic) are most often decoded by a threshold method (Threshold decoding – TD), and the second (nonsystematic) - with the using of sequential decoding algorithm (SDA) or the Viterbi algorithm (VA). Currently nonsystematic convolutional codes decoded by Viterbi algorithm, are widely used in communication systems.

Concatenated codes are divided into 2 classes: serial and parallel, which distinguish how the encoders include in the channel – serially or parallel. The most known example of the parallel concatenated codes is turbo codes.

Date: 2015-02-16; view: 1054