Joint Source Channel Coding for Satellite Transmission

The Viterbi algorithm essentially performs maximum likelihood decoding; however, it reduces the computational complexity load by taking advantage of the special structure in the code trellis. The advantage of Viterbi coding is that the complexity of a Viterbi decoder is not a function of the number of symbols in the codeword sequence.

The algorithm involves calculating trellis paths that could not possibly be candidate for maximum likelihood choice. When two path enter the same state, the one having the best metric is chose; this path is called the surviving path. This selection of surviving path is performed for all the states. The decoder continues in this way to advance deeper into the trellis, making decision by eliminating the least likely path. The early rejection of the unlikely path reduces the complexity.

Decoder trellis diagram

BCH (Bose, Chaudhuri, Hocquenghem ) codes are a class of linear and cyclic block codes that can be considered as a generalization of the Hamming codes, as they can be designed for any value of the error-correction capability t. These codes are defined in the binary field GF(2), and also in their non-binary version, over the Galois field GF(q).

BCH codes are a generalization of Hamming codes, and they can be designed to be able to correct any error pattern of size t or less [1, 2, 4]. In this sense the generalization of the Hamming codes extends the design of codes for t = 1 (Hamming codes) to codes for any desired higher value of t (BCH codes). The design method is based on taking an LCM of appropriate minimal polynomials, as described in the previous section for a particular example.

For any positive integer m ≥ 3 and t < 2m−1, there exists a binary BCH code CBCH(n, k) with the following properties:

Code length n = 2m − 1

Number of parity bits n − k ≤ mt

Minimum Hamming distance dmin ≥ 2t + 1

Error-correction capability t errors in a code vector

These codes are able to correct any error pattern of size t or less, in a code vector of length n, n = 2m − 1.

The generator polynomial of a BCH code is described in terms of its roots, taken from the Galois field GF(2m). If α is a primitive element in GF(2maxi), the generator polynomial g(X) of a BCH code for correcting t errors in a code vector of length n = 2m − 1 is the minimum-degree polynomial over GF(2) that has α, α2, . . . , α2t as its roots:

g(αi ) = 0, i = 1, 2, . . . , 2t
It also true that g(X) has αi and its conjugate as its roots (see Appendix B). On the other hand, if Φi (X) is the minimal polynomial of αi then the LCM of Φ1(X), Φ2(X), . . . , Φ2t (X) is the generator polynomial g(X):
g(X) = LCM{Φ1(X),Φ2(X), . . . Φ2t (X)}

As a result of the definition of a linear binary block BCH code CBCH(n, k) for correcting error patterns of size t or less, and with code length n = 2m − 1, it is possible to affirm that any code polynomial of such a code will have α, α2, . . . , α2t and their conjugates as its roots. This is so because any code polynomial is a multiple of the corresponding generator polynomial g(X), and also of all the minimal polynomials Φ1(X), Φ2(X), . . . , Φ2t (X).

Any code polynomial c(X) = c0 + c1X + . . . + cn−1Xn−1 of CBCH(n, k) has primitive element αi as a root:
c(αi ) = c0 + c1αi + •• •+cn−1αi (n−1) = 0

The code polynomial, the error polynomial and the received polynomial are related by the following expression:

r (X) = c(X) + e(X) (16)

Syndrome decoding can be used with BCH codes, as they are linear cyclic block codes. Recall that, for a given code polynomial c(X), c(αi ) = 0, and that this is equivalent to
c ◦ HT = 0

Combining this expression with that used to calculate the syndrome vector,
S = (s0, s1, . . . , s2t ) = r ◦ HT

and the following set of equations is obtained:

si = r (αi ) = e(αi ) = r0 + r1(αi ) + •• •+rn−1(αi )n−1

with 1 ≤ i ≤ 2t.

These equations allow us to calculate the ith component of the syndrome vector by replacing the variable X with the root αi in the received polynomial r(X). The syndrome vector consists of elements of the Galois field GF(2m). Another method of evaluating these elements proceeds in the following way: The received polynomial is first divided by Φi (X), which is the minimal polynomial corresponding to the root αi , so that Φi (αi ) = 0, and then

r (X) = ai (X) Φi (X) + bi (X)

which gives, when substituting αi ,

r (αi ) = bi (αi )