Method and circuit for decoding convolutional codes

A simple decoder which decodes convolutional codes of constraint length K and coding rate R=n/m, generated by the modulo-2 addition of data selected from original data of consecutive K+n-1 bits in accordance with coupling coefficients of m code generating vectors each composed of predetermined K+m-1 coupling coefficients, where K, n and m are natural numbers, K being larger than 1 and m being larger than n, said simple decoder comprising:

• a shift register supplied with received data of said convolutional codes on a bitwise basis and having N series-connected shift stages, where N is an integer which satisfies N.gtoreq.m (K-1)/(m-n), said N shift stages constituting a shift register circuit for holding N pieces of N encoded data;
• n selective coupling means each for delivering the outputs from a plurality of stages selected from said N shift stages in accordance with a corresponding one of n sets of coupling coefficients each set of which are N elements in a corresponding one of n consecutive rows selected from a decoding generative matrix corresponding to a code generating vector of said encoder;
• and
• n modulo-2 addition circuit means connected to said n selective coupling means, each for performing modulo-2 addition of outputs in a corresponding one of said n groups selected from said plurality of shift stages;
• said decoding generative matrix being an inverse matrix of a square matrix whose elements are N.times.N coefficients of N code generating polynomials for generating N codes, produced using m code generating vectors of said encoder with respect to consecutive K+n-1 bits of original data input into said encoder every n bits.

A simple decoding method for receiving and decoding successive bits of convolutional codes of constraint length K and coding rate R=n/m, generated by repeating, for each input of original data into an encoder while shifting said original data by steps of n bits, an operation of outputting m-bit encoded data by the modulo-2 addition of each of data selected from consecutive K+n-1 bits of said original data input into said encoder in accordance with predetermined K+n-1 coupling coefficients, respectively, where K, n and m are natural numbers, K being larger than 1 and m being larger than n, said method comprising the steps of:

• holding the most recent consecutive N bits of said convolutional codes received by steps of m bits, where N is a predetermined integer which satisfies N.gtoreq.m (K-1)/(m-n);
• delivering n groups of output bits selected from said N bits in accordance with n corresponding sets of coupling coefficients each set of which are N elements in a corresponding one of n consecutive rows selected from a decoding generative matrix corresponding to the code generating vectors of said encoder;
• and
• performing the modulo-2 addition of said selected data in each of n groups and outputting n-bit decoded data;
• wherein said decoding generative matrix is an inverse matrix of a square matrix whose elements are N.times.N coefficients of N code generating polynomials for generating N codes, produced using m code generating vectors of said encoder with respect to consecutive K+n-1 bits of original data output into said encoder every n bits.

A method of forming a simple decoder which decodes convolutional codes of constraint length K and coding rate R=n/m, generated by repeating, for each input of original data into an encoder while shifting said original data by steps of n bits, an operation of outputting m-bit encoded data by the modulo-2 addition of each of data selected from consecutive K+n-1 bits of said original data input into said encoder in accordance with predetermined K+n-1 coupling coefficients, respectively, where K, n and m are natural numbers, K being larger than 1 and m being larger than n, said method comprising:

• a step of obtaining x sets of m-bit encoded data by repeating the generation of m-bit encoded data through use of m code generating vectors with respect to said original data of the most recent consecutive K+n-1 bits input each time said original data is input by steps of n bits, where x is a predetermined integer which satisfies x.gtoreq.(K-1)/(m-n);
• a step of obtaining N code generating polynomials each having N coupling coefficients, by representing each of m code generating polynomials for generating m-bit encoded data of each of said sets by N=xm coupling coefficients including said (K+n-1) coupling coefficients of a corresponding one of said m code generating vectors;
• a step of forming an N by N code generating matrix whose elements in each row are said N coupling coefficients of corresponding one of N code generating polynomials;
• a step of obtaining an inverse matrix from said code generating matrix;
• and
• a step wherein N shift stages, into which said convolutional codes are input, and each of n modulo-2 addition circuits are selectively connected in accordance with N coupling coefficients which are N elements of corresponding one of n consecutive rows selected from said inverse matrix.

A decoder system comprising:

• a simple decoder for decoding received convolutional codes to obtain estimated original data, said convolutional codes being of constraint length K and coding rate R=n/m, generated by the modulo-2 addition of data selected from original data of consecutive K+n-1 bits in accordance with coupling coefficients of m code generating vectors each composed of predetermined K+n-1 coupling coefficients, where K, n and m are natural numbers, K being larger than 1 and m being larger than n, said simple decoder comprising m shift registers each supplied with one bit of sequentially received m-bit data of said convolutional codes and having x series-connected shift stages, where x is a predetermined integer which satisfies x.gtoreq.(K-1)/(m-n), a total of N=mx shift stages of said m shift registers forming a shift register circuit for storing N pieces of encoded data;
• n selective coupling means each for delivering the outputs from a plurality of stages selected from said N shift stages in accordance with a corresponding one of n sets of coupling coefficients each set of which are N elements in a corresponding one of n consecutive rows selected from a decoding generative matrix corresponding to a code generating vector of said encoder, and n modulo-2 addition circuit means connected to said n selective coupling means, each for performing modulo-2 additions of outputs in a corresponding one of said n groups selected from said plurality of shift stages;
• said decoding generative matrix being an inverse matrix of a square matrix whose elements are N.times.N coefficients of N code generating polynomials which generates N=mx codes produced using m code generating vectors of said encoder;
• an encoder of the same construction as that of an encoder at the transmitting side, for re-encoding estimated original data from said simple decoder by convolution;
• compare means for comparing said received encoded data and said re-encoded data by an exclusive OR operation therebetween;
• a Viterbi decoder for decoding an estimated error from the results of comparison by said compare means;
• and
• modulo-2 addition circuit means for correcting said estimated error of said estimated original data by performing a modulo-2 addition of said estimated original data from said simple decoder and said estimated error from said Viterbi decoder.

A transmission line quality monitoring apparatus comprising:

• a simple decoder for obtaining estimated original data by decoding received convolutional codes, said convolution codes being of constraint length K and coding rate R=n/m, generated by the modulo-2 addition of data selected from original data of consecutive K+n-1 bits in accordance with coupling coefficients of m code generating vectors each composed of predetermined K+n-1 coupling coefficients, where K, n and m are natural numbers, K being larger than 1 and m being larger than n, said simple decoder comprising m shift registers each supplied with one bit of sequentially received m-bit data of said convolutional codes and having x series-connected shift stages, where x is a predetermined integer which satisfies x.gtoreq.(K-1)/(m-n), a total of N=mx shift stages of said m shift registers forming a shift register circuit for storing N pieces of encoded data;
• n selective coupling means each for delivering the outputs from a plurality of stages selected from said N shift stages in accordance with a corresponding one of n sets of coupling coefficients each set of which are N elements in a corresponding one of n consecutive rows selected from a decoding generative matrix corresponding to a code generating vector of said encoder;
• and n modulo-2 addition circuit means connected to said n selective coupling means, each for performing modulo-2 additions of outputs in a corresponding one of said n groups selected from said plurality of shift stages;
• said decoding generative matrix being an inverse matrix of a square matrix whose elements are N.times.N coefficients of N code generating polynomials which generates N=mx codes produced using m code generating vectors of said encoder;
• a convolutional encoder of the same construction as that of an encoder at the transmitting side, for re-encoding said estimated original data from said simple decoder by convolution;
• compare means for comparing said received encoded data and said re-encoded data by an exclusive OR operation therebetween to detect a mismatch;
• and
• counter means for counting the number of mismatches detected by said compare means and for outputting an evaluation value corresponding to the count value.

A decoder system comprising:

• a simple decoder for decoding received convolutional codes to obtain estimated original data, said convolutional codes being of constraint length K and coding rate R=n/m, generated by the modulo-2 addition of data selected from original data of consecutive K+n-1 bits in accordance with coupling coefficients of m code generating vectors each composed of predetermined K+n-1 coupling coefficients, where K, n and m are natural numbers, K being larger than 1 and m being larger than n, said simple decoder comprising a shift register supplied with received data of said convolutional codes on a bitwise basis and having N series-connected shift stages, where N is an integer which satisfies N.gtoreq.m (K-1)/(m-n, said N shift stages constituting a shift register circuit for holding N pieces of N encoded data;
• n selective coupling means each for delivering the outputs from a plurality of stages selected from said N shift stages in accordance with a corresponding one of n sets of coupling coefficients each set of which are N elements in a corresponding one of n consecutive rows selected from a decoding generative matrix corresponding to a code generating vector of said encoder;
• and n modulo-2 addition circuit means connected to said n selective coupling means, each for performing modulo-2 addition of outputs in a corresponding one of said n groups selected from said plurality of shift stages;
• said decoding generative matrix being an inverse matrix of a square matrix whose elements are N.times.N coefficients of N code generating polynomials for generating N axes, produced using m code generating vectors of said encoder with respect to consecutive K+n-1 bits of original data input into said encoder every n bits;
• an encoder of the same construction as that of an encoder at the transmitting side, for re-encoding estimated original data from said simple decoder by convolution;
• compare means for comparing said received encoded data and said re-encoded data by an exclusive OR operation therebetween;
• a Viterbi decoder for decoding an estimated error from the results of comparison by said compare means;
• and
• modulo-2 addition circuit means for correcting said estimated error of said estimated original data by performing a modulo-2 addition of said estimated original data from said simple decoder and said estimated error from said Viterbi decoder.

A transmission line quality monitoring apparatus comprising:

• a simple decoder for obtaining estimated original data by decoding received convolutional codes being of constraint length K and coding rate R=n/m, generated by the modulo-2 addition of data selected from original data of consecutive K+n-1 bits in accordance with coupling coefficients of m code generating vectors each composed of predetermined K+m-1 coupling coefficients, where K, n and m are natural numbers, K being larger than 1 and m being larger than n, said simple decoder comprising a shift register supplied with received data of said convolutional codes on a bitwise basis and having N series-connected shift stages, where N is an integer which satisfies N.gtoreq.m (K-1)/(m-n), said N shift stages constituting a shift register circuit for holding N pieces of N encoded data;
• n selective coupling means each for delivering the outputs from a plurality of stages selected from said N shift stages in accordance with a corresponding one of n sets of coupling coefficients each set of which are N elements in a corresponding one of n consecutive rows selected from a decoding generative matrix corresponding to a code generating vector of said encoder;
• and n modulo-2 addition circuit means connected to said n selective coupling means, each for performing modulo-2 addition of outputs in a corresponding one of said n groups selected from said plurality of shift stages;
• said decoding generative matrix being an inverse matrix of a square matrix whose elements are N.times.N coefficients of N code generating polynomials for generating N axes, produced using m code generating vectors of said encoder with respect to consecutive K+n-1 bits of original data input into said encoder every n bits;
• a convolutional encoder of the same construction as that of an encoder at the transmitting side, for re-encoding said estimated original data from said simple decoder by convolution;
• compare means for comparing said received encoded data and said re-encoded data by an exclusive OR operation therebetween to detect a mismatch;
• and
• counter means for counting the number of mismatches detected by said compare means and for outputting an evaluation value corresponding to the count value.