Error detection and correction capability of block codes

Let's establish dependence of detecting and correcting capability of the block codes from a code parameters. it is useful to consider a binary code with parameters n = 3, k = 2. All words of this code (M = 8) it is possible to divide by sign «parity of units number in a code words» on two groups:

– words with even number of units,

– words with odd number of units.

The code constructed by this principle named “code with even number of units” is considered in theExercise 2.1.

Example 3.1 A binary code (m = 2, n = 3) with even number of units.

In table 3.1 the full set of binary words (m = 2, n = 3, M = 8) is divided into a set of the allowedcode words (M ₀ = 4) containing words with even number of units (including the word 000 (number 0 – even)), and the set of the forbidden words withodd number of units. Their total quantity is equal to difference M _forbid = M – M ₀ = 4.

table 3.1 – code with even number of units

Full set of a words (M= 8): {000, 001, 010, 011, 100, 101, 110, 111}
theallowedcode words (with even number of units), M 0=4: {000, 011, 101, 110}	the forbiddenwords (with odd number of units), M forbid = M – M 0 = 4: {001, 010, 100, 111}
Code parameters: code rate R code =1/2, code distance d min = 2, code can detect q det = 1 error

allowed code words are used for an information transfer through channel (are allowed for transfer).

forbidden code words are not used for an information transfer through channel (are forbiddenfor transfer).

In the coding theory the concept «distance between code words» plays the important role. Everyone binary block error-control code are characterized by a parameter code distance. The code distance d _min is one of the major parameters of error-control codes.

The code distance of the binary error-control code d _min is the minimal Hamming distance [3] between the allowed code words. Let consider a pairs of allowed code words from table 3.1. it is possible to establish that for this code a minimal distance is d _min = 2. Such distance allows to detect asingle errorsin the channel. If the transmitted code word is b = (1 1 0), and channel error is characterized by a word (error vector ) e = (0 1 0) the received word with error on the channel exit is defined by module-2 addition:

b = 1 1 0,

e = 0 1 0,

=(a e) = 1 0 0.

From this it is visible, that the symbol «1» in error vector e changesa corresponding symbol in transmitted word b to an opposite symbol.

For the characteristic of quantity of channel errors enter concept the multiplicity of an errors. multiplicity of an errors q is a quantity of the channel errors within a codeword. For example, for words from table 3.1 the error vector variants withmultiplicity q = 1 are: e = 100, 010, 001. And the double errors are: 110, 011, 101.

The code capability to detect and to correct of errors depends from code distance d _min.

Error detection is the fixing by decoding ofan error presence of certain multiplicity in received word .

error correction is the detectionby decoding of an errors in certain symbols of received words and their subsequent correction.

According to these definitions error-control codes are subdivided into following classes:

1 error-detecting codes which detect a channel errors.

2 Error-control codes which correct a channel errors andnamed in literature as codes with direct correction of errors(i.e. with errors correction by a code methods).

The relation between code distance d _min and error control ability of a code we will establish on an example of code with even number of units (see table 3.1). it is convenient to use a geometrical representation of code words on figure 3.1. Let's represent a code words by set from three symbols (x, y, z) and values of these symbols will choose from the binary alphabet {0, 1}. It is possible to represent all possible code words by the points in the Cartesian system with coordinates (x, y, z). Thus words will form tops of a three-dimensional cube. On figure 3.1 these tops are marked as follows:

– By the sign "•" notes the allowed code words,

– by the sign "r" notes the forbidden code words.

It is visible, that code structure is thatbetween the allowed code words are forbidden words. They form the«protective interval». Therefore the action of any single error translates any allowed word to the nearest forbidden words. This property leads to such decoding rule of a code with even units number and detection of any single errors: reception from the channel output of the forbidden code words allows to assert that in the channel there was anysingle error. It is easy to be convinced that this code does not allow to detect double errors (because «protective interval» is nonsufficient ). By induction it is possible to prove, thatany binary code with even number of units allowsto detect any errors if their multiplicity is odd anddoes not detectany errorsif their multiplicity is even. The concept of «a protective interval» is easily applicable for a study of the relation between code distance and code ability to correct of an errors. If the minimum distance between allowed code words (code distance) is d _min, that as is shown from figure 3.2 the protective interval contains(d _min ‑ 1) forbidden wordsand for "transfer" of each allowed word to nearest allowed word it is necessary by errors to make (d _min – 1) "steps". Clearly, that all errors with multiplicity q= 1, 2, 3,..., (d _min – 1) can be detected.

From here follows, that if code distance of a binary code is d _min code ability to detect of errors with multiplicity q _detis defined as:

(3.1)

Let's take advantage of similar representation for estimations of ability to correct of errors. On figure 3.3 layout of the allowed code words b _allow.1 and b _allow.2 is shown.between them are allocated (d _min – 1) the forbidden words. Let's divide all set of the words on two allowed subset as is shown in a figure 3.3. If for example the received word is allocated into «allowed decoding subset of a word b _allow.1» that during the decoding becomes decision about transmitting of the word b _allow.1, i.e. thereby the error transitions of word b _allow.1 to the nearestforbidden words are corrected. It is similarly possible to explain error control process by the transmission of the word b _allow.2. It is visible, that distance of each allowed subset is (d _min – 1)/2 (by d _min is odd). it defines code error control ability. For even values d _min the distance of each allowed subset is [(d _min/2) – 1], that also defines error-control ability of a code.

Thus, if code distance of a binary error control code is d _min code ability to correct of errors is defined by expressions:

, if (d _min – odd) and , if (d _min – even). (3.2)