bchdec

BCH decoder

Syntax

decoded = bchdec(code,N,K)

decoded = bchdec(code,N,K,paritypos)

[decoded,cnumerr] = bchdec(___)

[decoded,cnumerr,ccode] = bchdec(___)

Description

decoded = bchdec(code,N,K) attempts to decode the received signal in code using an (N,K) BCH decoder with the narrow-sense generator polynomial. Parity symbols are at the end and the leftmost symbol is the most significant symbol.

In the decoded Galois field array, each row represents the attempt at decoding the corresponding row in code.

decoded = bchdec(code,N,K,paritypos) specifies in paritypos whether the parity symbols in code were appended or prepended to the message in the coding operation.

[decoded,cnumerr] = bchdec(___) returns a column vector, cnumerr, where each element is the number of corrected errors in the corresponding row of code. You can return cnumerr with either of the preceding syntaxes.

[decoded,cnumerr,ccode] = bchdec(___) returns ccode, the corrected version of code.

Examples

Results of Error Correction

BCH-decode an input that has more errors per codeword than the error correcting capability of the BCH decoder. Decode a BCH coded message with two errors per codeword using a single-error correcting BCH decoder. View the effects of the error mismatch on the output codeword.

Check the number of errors per codeword a [63,57] BCH decoder is capable of correcting.

n = 63; 
k = 57;
t = bchnumerr(n,k)

t = 
1

The [63,57] BCH decoder is capable of correcting one error per codeword.

Create a random stream and use it to generate a GF array. Encode the message.

s = RandStream('swb2712','Seed',9973);
msg = gf(randi(s,[0 1],1,k));
code = bchenc(msg,n,k);

Add two errors per codeword and decode the errored code.

cnumerr2 = zeros(nchoosek(n,2),1);
nErrs = zeros(nchoosek(n,2),1);
cnumerrIdx = 1;
for idx1 = 1 : n-1
    %sprintf('idx1 for 2 errors = %d', idx1)
    for idx2 = idx1+1 : n
        errors = zeros(1,n);
        errors(idx1) = 1;
        errors(idx2) = 1;
        erroredCode = code + gf(errors);
        [decoded2, cnumerr2(cnumerrIdx)] ...
          = bchdec(erroredCode,n,k);

Encode the decoded message. Check that the re-encoded message differs from the errored message in only one bit.

        if cnumerr2(cnumerrIdx) == 1
            code2 = bchenc(decoded2,n,k);
            nErrs(cnumerrIdx) = biterr(double(erroredCode.x), ...
              double(code2.x));
        end        
        cnumerrIdx = cnumerrIdx + 1;    
    end
end

Plot the computed number of errors, based on the difference between the doubly-errored code and the re-encoded version of the initial decoding.

plot(nErrs)
title('Number of Actual Errors')

All inputs with two errors were decoded to a codeword that differs in exactly one bit from the re-encoded version.

Decode Received BCH Codeword in Noisy Channel

Set the BCH parameters for a Galois array of GF(2).

M = 4;
n = 2^M-1;   % Codeword length
k = 5;       % Message length
nwords = 10; % Number of words to encode

Create a message.

msgTx = gf(randi([0 1],nwords,k));

Find the error-correction capability.

t = bchnumerr(n,k)

t = 
3

Encode the message.

enc = bchenc(msgTx,n,k);

Corrupt up to t bits in each codeword.

noisycode = enc + randerr(nwords,n,1:t);

Decode the noisy code.

msgRx = bchdec(noisycode,n,k);

Validate that the message was properly decoded.

isequal(msgTx,msgRx)

ans = logical
   1

Increase the number of possible errors, and generate another noisy codeword.

t2 = t + 1;
noisycode2 = enc + randerr(nwords,n,1:t2);

Decode the new received codeword.

[msgRx2,numerr] = bchdec(noisycode2,n,k);

Determine if the message was properly decoded by examining the number of corrected errors, numerr. Entries of -1 correspond to decoding failures, which occur when the codeword has more errors than can be corrected for the specified [n,k] pair.

numerr

numerr = 10×1

     1
     2
    -1
     2
     3
     1
    -1
    -1
     2
     3

Two of the ten transmitted codewords were not correctly received.

Input Arguments

code — Encoded message

Galois field array

Encoded message, specified as a Galois field array of symbols over GF(2). Each N-element row of code represents a corrupted systematic codeword.

For more information, see Creating a Galois field array.

N — Codeword length

integer

Codeword length, specified as an integer of the form N = 2^M–1, where M is an integer from 3 to 16. See Tips for information about valid N values, valid (N,K) pairs, and error correcting capabilities for a given BCH code.

Example: 15 for M=4

K — Message length

integer

Message length, specified as an integer. N and K must produce a narrow-sense BCH code.

Example: 5 specifies a Galois field array with five elements.

paritypos — Parity position

'end' (default) | 'beginning'

Parity position, specified as 'end' or 'beginning'. Parity symbols are at the end or beginning of each word in the output Galois field array. If paritypos is 'beginning', then a decoding failure causes bchdec to remove N-K symbols from the beginning rather than the end of the row.

Output Arguments

decoded — Decoded message

Galois field array of symbols over GF(2)

Decoded message, returned as a Galois field array of symbols over GF(2). Each row represents the attempt at decoding the corresponding row in code. A decoding failure occurs if bchdec detects more than T errors in a row of code, where T is the number of errors per codeword that the decoder is capable of correcting. When a decoding failure occurs, bchdec forms the corresponding row of decoded by removing N-K symbols from the end of the row of code. For more information, see Error Correcting Capability.

cnumerr — Number of corrected errors

column vector

Number of corrected errors in the corresponding row of code, returned as a column vector. A value of –1 in cnumerr indicates a decoding failure in that row in code.

ccode — Corrected version of code

Galois field array

Corrected version of code, returned as a Galois field array. ccode has the same format as the input code. If a decoding failure occurs in a certain row of code, the corresponding row in ccode contains that row unchanged.

More About

Error Correcting Capability

BCH decoders correct up to a specified number of errors per codeword based on the (N,K) pair used to BCH encode that message. The error correcting capability, T, of a given (N,K) pair is returned by bchnumerr. See Tips for information about valid N values, valid (N,K) pairs, and error correcting capabilities for a given BCH code.

If the coded message contains more errors per codeword than the decoder is capable of correcting, the decoder is unlikely to decode to the correct codeword. For example, when a single-error-correcting BCH decoder (T=1) is given an input with two errors per codeword, it decodes it to a valid codeword but not the correct codeword. When a double-error-correcting BCH decoder (T=2) is given an input with three errors per codeword, the decoder sometimes decodes to an invalid codeword. The cnumerr and ccode output provide feedback to analyze the correctness of the decoded message.

Tips

• To generate the list of valid (N,K) pairs along with the corresponding values of the error-correction capability, run bchnumerr(N).

• Valid values for N = 2^M–1, where M is an integer from 3 through 16. The maximum allowable value of N is 65,535.

Algorithms

bchdec uses the Berlekamp-Massey decoding algorithm. For information about this algorithm, see the works listed in References.

References

[1] Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Upper Saddle River, NJ: Prentice Hall, 1995.

[2] Berlekamp, Elwyn R. Algebraic Coding Theory. New York: McGraw-Hill, 1968.

Version History

Introduced before R2006a