Coding and decoding of block code

In the center of the block coding theory is the concept of a generator matrix (4.1) and (4.2). If a = | a ₀, a ₁,..., a_k | – row-matrix of a primary code the coding rule of a block codeis defined by the product

b = aG,(5.1)

where a = | a ₀, a ₁,..., a_k | – row-matrix of primary code at encoder input,

b = | b ₀, b ₁,..., b_n | – row-matrix of block code word at encoder output,

G – generator matrix of linear (n, k) code.

Example 5.1 The encoder of code (7,4).

The encoder structure of a systematic code (7,4) is defined by generator matrix (4.4) and coding rule (5.1). If on encoder input is the symbols row of a primary code a = (a ₁, a ₂, a ₃, a ₄) then symbols of allowed code word on its output

b = (b ₁, b ₂, b ₃, b ₄, b ₅, b ₆, b ₇) are defined by following equalities:

b ₁ = a ₁, b ₂ = a ₂, b ₃ = a ₃, b ₄ = a ₄,
b ₅ = a ₁ a ₂ a ₃ a ₄, b ₆ = a ₁ a ₂ a ₄, b ₇ = a ₁ a ₃ a ₄. (5.2)

On figure 5.1 the structure of encoder of systematic code (7,4) with equalities (5.2) is shown.

By the decoding of block codes the check relations establish with use of the parity check matrix H which space of rows is orthogonal to space of rows of generator matrix, that is:

G · H ^T = 0. (5.3)

Here T– an index a transposition.

If generator matrix is set in the form (4.2) for performance of a orthogonality condition the parity check matrix should look like:

H = (P ^Tï I _{n - k} ), (5.4)

where P ^T– transposed submatrix P of generator matrix G,

I _n-k – identity matrix a size (n – k) ´ (n – k).

Exercise 5.1 The parity check matrix of a systematic code (7,4).

The generator matrix of systematic code (4.7) is set:

.

According to rule (5.4) form parity check matrix of this code.

Solution. Sequentially we discover the submatrixes entering into the formula (5.4). The transposed submatrix by size (n – k) ´ k:

,

The identity submatrix by size (n – k) ´ (n – k):

.

We unite submatrixes in the uniform parity check matrix of code:

. (5.5)

From orthogonality condition of generator and parity check matrixes of linear code (5.3) follows that each allowed word of linear code generated by rule b = a×G also satisfiesto the orthogonality condition:

b · H ^T = a · G · H ^T = 0. ( 5.6)

By transmission through the channel code symbols are distorted. The received words look like = b Å e, where b = (b ₀, b ₁,..., b_n), and an error vector
е = (е ₀, е ₁,..., е_n). By decoding calculate a syndrome vector

S = · H ^T = (s ₀, s ₁,..., s_{n–k –1}). (5.7)

The syndrome depends only on an error vector:

S = · H ^T = (b Å e) H ^T = · H ^T Å e · H ^T.

As the condition of orthogonality · H ^T= 0 is satisfied, the syndrome is equal:

S = e · H ^T (5.8)

From here the simple rule of the error detection follows:

1 If the syndrome S = 0 then an error vector е = 0, i.e. in the channel there were no errors and the received word belongs to set of the allowedcode words.

2 If S ≠ 0 word contains errors. It is possible by the syndrome symbols to define a configuration of the error vector.

This principle underlies syndrome decoding.