bchdec

Syntax

decoded = bchdec(code,n,k)
decoded = bchdec(...,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. code is a Galois array of symbols over GF(2). Each n-element row of code represents a corrupted systematic codeword, where the parity symbols are at the end and the leftmost symbol is the most significant symbol.

In the Galois array decoded, 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 correctable errors as reported by bchgenpoly. In the case of a decoding failure, bchdec forms the corresponding row of decoded by merely removing n-k symbols from the end of the row of code.

decoded = bchdec(...,paritypos) specifies whether the parity symbols in code were appended or prepended to the message in the coding operation. The string paritypos can be either 'end' or 'beginning'. The default is 'end'. 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.

[decoded,cnumerr] = bchdec(...) returns a column vector cnumerr, each element of which is the number of corrected errors in the corresponding row of code. A value of -1 in cnumerr indicates a decoding failure in that row in code.

[decoded,cnumerr,ccode] = bchdec(...) returns ccode, the corrected version of code. The Galois array ccode has the same format as code. If a decoding failure occurs in a certain row of code, the corresponding row in ccode contains that row unchanged.

Results of Error Correction

BCH decoders correct up to a certain number of errors, specified by the user. If the input contains more errors than the decoder is meant to correct, the decoder will most likely not output the correct codeword.

The chance of a BCH decoder decoding a corrupted input to the correct codeword depends on the number of errors in the input and the number of errors the decoder is meant to correct.

For example, when a single-error-correcting BCH decoder is given input with two errors, it actually decodes it to a different codeword. When a double-error-correcting BCH decoder is given input with three errors, then it only sometimes decodes it to a valid codeword.

The following code illustrates this phenomenon for a single-error-correcting BCH decoder given input with two errors.

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

% Add 2 errors
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);
        
        % If bchdec thinks it corrected only one error,
        % then encode the decoded message.  Check that
        % the re-encoded message differs from the errored
        % message in only one coordinate.
        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 double-errored codeword and the codeword that was
% re-encoded from the initial decoding.
plot(nErrs)
title(['Number of Actual Errors between Errored Codeword and' ...
 'Re-encoded Codeword'])

The resulting plot shows that all inputs with two errors are decoded to a codeword that differs in exactly one position.

Examples

The script below encodes a (random) message, simulates the addition of noise to the code, and then decodes the message.

m = 4; n = 2^m-1; % Codeword length
k = 5; % Message length
nwords = 10; % Number of words to encode
msg = gf(randi([0 1],nwords,k));
% Find t, the error-correction capability.
[genpoly,t] = bchgenpoly(n,k);
% Define t2, the number of errors to add in this example.
t2 = t;

% Encode the message.
code = bchenc(msg,n,k);
% Corrupt up to t2 bits in each codeword.
noisycode = code + randerr(nwords,n,1:t2);
% Decode the noisy code.
[newmsg,err,ccode] = bchdec(noisycode,n,k);
if ccode==code
   disp('All errors were corrected.')
end
if newmsg==msg
   disp('The message was recovered perfectly.')
end

In this case, all errors are corrected and the message is recovered perfectly. However, if you change the definition of t2 to

t2 = t+1;

then some codewords will contain more than t errors. This is too many errors, and some are not corrected.

Limitations

The maximum allowable value of n is 65535.

More About

expand all

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.

See Also

|

Was this topic helpful?