TECHNICAL FIELD

The present disclosure relates to an encoding and/or decoding device, which uses a modified channel code that is modified from an original channel code. The present disclosure also relates to a code generator for generating a modified code from an original code by modifying the original code. In particular, the modified code, which is defined by a check matrix, is obtained by modifying a check matrix defining the original code. The present disclosure also relates to a channel code generating method.

BACKGROUND

Channel codes are essential in all digital communications systems. A typical system for forward error correction (FEC) coding, also called a coding scheme, is shown inFIG. 7. The system includes an encoder (at the transmitter side) and a decoder (at the receiver side), which are connected via a communication channel. The encoder adds redundancy to data to be transmitted in the communication channel, i.e. adds redundant data. The decoder exploits this redundancy to correct transmission errors, such that the receiver ideally obtains the transmitted data free of errors despite noise in the communication channel.

In particular, inFIG. 7, the data u to be transmitted (termed “information word”) is given to the encoder, which produces a codeword x containing redundancy. This codeword x is then transmitted over the noisy communication channel, which typically introduces errors. The output vector y is provided to the decoder, which produces estimates of the transmitted codeword x and the transmitted data u. A set C of possible codewords is called the code (or channel code), and the following description is particularly concerned with such a code.

For reasons of complexity at the encoder and decoder sides, typically linear codes over finite fields are employed. The following explanation is thus provided for the finite field F2={0, 1} of size 2—for the sake of simplicity. However, the following explanation holds in a similar manner for other fields or rings. In particular, a code C of length N and dimension K (labelled in the present disclosure as an ‘{N, K} code’), may be defined by a generator matrix G of size K×N as:
C={x=u·G:u∈F2K}

In that case, the encoder that maps the information word u of length K to the codeword x of length N is given by
x=u·G
where addition and multiplication are over the binary field {0, 1}. Alternatively, the code C may be defined by the parity check matrix H (hereinafter “check matrix”) of size (N−K)×N as:
C={x∈F2N:x·HT=0}

By this definition a vector x is a codeword if and only if,
x·HT=0
For a given generator matrix, check matrices can be determined, and vice versa.

In a communication system, the information word u is encoded into the codeword x, and this codeword x is then transmitted over the noisy communication channel, yielding the observation vector y of length N. Based on the observation vector y, the decoder determines the most-likely codeword (codeword estimate) {circumflex over (x)} and the corresponding information word (information word estimate) û. This is called decoding.

For example, the maximum-likelihood (ML) decoder minimises the probability of a wrong decision, however, often at high decoding complexity. Other decoding methods, like Chase decoding or syndrome decoding, typically approximate this decision under lower decoding complexity.

An important property of a channel code is its minimum distance d, which is the minimum Hamming distance, i.e. the number of different positions between any two codewords. Due to the linearity of the code, this is also equal to the minimum Hamming weight, i.e. the number of non-zero positions of any code word. A second important property of a channel code is the number of such minimum-distance codewords, also called the multiplicity. The minimum distance together with its multiplicity determine the error rate of a code under ML decoding and many other decoding methods at low noise levels.

Two conventional methods to modify length N or dimension K of a given code are so-called ‘shortening’ and ‘extending’. The effect of these operations on the check matrix of a code is depicted inFIG. 8. Assumed is specifically an {N, K} code with check matrix H. Shortening the code by p positions leads to an {N−p, K−p} code, i.e. both length N and dimension K are reduced by p. The check matrix H′ of the shortened code can be obtained from the check matrix H by removing p columns such that the rank of the matrix does not change. Extending by q positions leads to an {N+q, K} code, i.e. the length N increases by q and the dimension K stays the same. The check matrix H″ of the extended code can be obtained from the check matrix H by first adding q zero columns and then adding q rows in a way such that the rank of the matrix increases by q.

For many good algebraic codes, like Hamming codes or Bose-Chaudhuri-Hocquenghem (BCH) codes, efficient decoding algorithms are available, i.e. algorithms that achieve low error rates at low decoding complexity. Such codes, however, are only available for specific values of length N and dimension K. If an application requires other lengths or dimensions, e.g. requires an {N′, K′} code while so far only {N, K} codes are provided, new decoding algorithms need to be developed to match the specific {N′, K′} code. These algorithms may be less efficient than those for the {N, K} codes, even if N′ and K′ are close to N and K.

A conventional way of constructing a new code {N′, K′} from and original {N, K} code—with the constraints defined above—is illustrated inFIG. 9in terms of the check matrices of the codes. The original code is first extended to the desired length N′ and then expurgated to the desired dimension K′ thus adding further check constraints. The process shown inFIG. 9in terms of the check matrices is as follows: starting from the check matrix H of the original code, conventionally, first q zero columns are appended to H, and then q+p rows are added to obtain the check matrix H′ of the new code.

Since the q+p new check constraints are adjoined in an unstructured way, a decoder of the original {N, K} code cannot be used efficiently to decode the new {N′, K′} code.

SUMMARY

In view of the above-mentioned problems and disadvantages, the present invention aims to improve the conventional code modification schemes. In particular, one of the objectives of example embodiments of the present invention is to provide a code generator for generating a modified code from an original code such that the modified code can be efficiently reused by a decoder (or encoder) of the original code. The present invention aims also for an encoding and/or decoding device that operates efficiently based on the modified code. In particular, in example embodiments of the present invention, the original code may be modified by increasing its code length N and at the same time decreasing its code dimension K such that a decoder for the new {N′, K′} code can efficiently reuse the decoder of the original {N, K} code.

Such a decoder is illustrated inFIG. 10. The decoder is originally a decoder of the original {N, K} code, i.e. it decodes the observation vector y with the original code to obtain the codeword estimate {circumflex over (x)} and the information word estimate û. However, the decoder can also use the new {N′, K′} code for performing this decoding.

In example embodiments of the present invention, an original code is modified in a specific manner, e.g., by a combined shortening and extending operation, to obtain a new code (a modified code). The obtained new code can be efficiently used by an existing decoder of the original code.

A first aspect of the present invention provides a device for encoding and/or decoding data transmitted in a communication channel, the device being configured to encode and/or decode the data based on an {N′, K′} code generated from an {N, K} code, wherein N and N′ are code lengths, K and K′ are code dimensions, N′−N=q>0, and K−K′=p>0, and wherein the {N′, K′} code is defined by a check matrix, the check matrix includes {N−K+p+q} rows and {N+q} columns, {N−K} elements in each of {p+q} columns of the check matrix are all zeros, and {N−K} elements in each of the remaining {N−p} columns of the check matrix are the elements of a check matrix defining the {N, K} code.

Advantageously, the device of the first aspect may use the new {N′, K′} code for encoding the data, allowing a decoder of the original {N, K} code to efficiently reuse the modified code. Further, the device of the first aspect may efficiently reuse the new {N′, K′} code for decoding the data, if it is a decoder of the original code. The device of the first aspect may even perform efficient encoding and/or efficient decoding on the data based on both the new {N′, K′} code and the original {N, K} code.

In the present disclosure, N, N′, K, K′, p, and q are natural numbers greater than zero.

In a possible implementation of the first aspect, the upper {N−K} elements of the left {p+q} columns of the check matrix are all zeros, and the upper {N−K} elements of the remaining {N−p} columns of the check matrix are the elements of the check matrix defining the {N, K} code.

This check matrix is an example that yields particularly good results in terms of minimum distance and reduced multiplicity of the new code. Row and/or column permutations may be applied to the check matrix of the new (modified) code, and the resulting check matrix would lead to the same results.

In a further implementation of the first aspect, the lower {p+q} elements of the left {p+q} columns of the check matrix build an identity matrix.

This allows for a particular simple implementation of the check matrix, and reduced computational complexity.

In a further implementation of the first aspect, each of the lower {p+q} rows is filled with alternating ones and zeros.

Preferably, any two adjacent rows of these lower {p+q} rows start with a one (first row) and a zero (second row), respectively. Thus, the adjacent rows are able to check odd and even indices of the code, respectively.

In a further implementation of the first aspect, the {N, K} and the {N′, K′} code are Hamming codes or Bose-Chaudhuri-Hocquenghem codes.

These codes are particularly good algebraic codes, and moreover perform well with the code construction scheme of the present disclosure.

In a further implementation of the first aspect, the {N, K} code is a Hamming code with N=127 and K=120, and the {N′, K′} code is a code with N′=128 and K′=119.

For this specific example, the minimum distance of the new code is the same as that of a new code constructed in a conventional manner, but its multiplicity is largely reduced. This significantly decreases error rates under both ML decoding and sub-optimal decoding methods.

In a further implementation of the first aspect, the device includes a code generator according to a second aspect of the present invention or any of its implementations.

The device may particularly be an encoder (in a transmitter or transceiver) and/or a decoder (in a receiver or transceiver) of data, specifically in a mobile communication system or an optical (fibre) communication system. The device is thus advantageously able to modify an original {N, K} code into a new {N′, K′} code, which can be efficiently reused. This allows for new applications that operate on other codes.

The second aspect of the present invention provides a code generator for generating an {N′, K′} code for encoding and/or decoding data transmitted in a communication channel from an {N, K} code, wherein N and N′ are code lengths, K and K′ are code dimensions, and the code generator is configured to shorten the {N, K} code to obtain an intermediate code, and extend the intermediate code to obtain the {N′, K′} code.

By applying a combined shortening and extending operation on the original {N, K} code the code generator of the first aspect is able to generate the new {N′, K′} code such that it can be efficiently reused by a decoder (and/or encoder) of the original code.

In an implementation of the second aspect, N′−N=q>0, K−K′=p>0, and the code generator is configured to shorten the {N, K} code by p positions to obtain an intermediate {N−p, K′} code, and extend the intermediate {N−p, K′} code by p+q positions to obtain the {N′, K′} code.

This new code yields particularly good results in terms of the minimum distance and reduced multiplicity.

In a further implementation of the second aspect, the code generator is configured to, for generating the {N′, K′} code from the {N, K} code, modify a first check matrix that defines the {N, K} code to obtain a second check matrix that defines the {N′, K′} code, the modification of the first check matrix including removing p columns of the first check matrix to obtain a first intermediate matrix, adding {p+q} left or right columns filled with all zeros to the first intermediate matrix to obtain a second intermediate matrix, and adding {p+q} rows to the second intermediate matrix to obtain the second check matrix.

The code generator can thus obtain an efficient new code by operating on the check matrix of the original code in a relatively simple manner. As an example, the p left columns of the first check matrix may be removed to obtain the first intermediate matrix. However, any p columns may be removed as long as the rank constraint is fulfilled. Further, {p+q} bottom rows may be added to the second intermediate matrix to obtain the second check matrix. However, the additional rows may be added above, below, or in between the other rows.

In a further implementation of the second aspect, the code generator is configured to set {p+q} elements of the left or right {p+q} columns of the second check matrix such that they build an identity matrix.

This allows for a particular simple implementation of the check matrix, and for reduced computational complexity. For example, the {p+q} elements may be the lower {p+q} elements of the left or right {p+q} columns of the second check matrix.

In a further implementation of the second aspect, the code generator is configured to set the elements of each of the {p+q} rows of the second check matrix such that it includes alternating ones and zeros.

Preferably, any two adjacent rows of these lower {p+q} rows start with a one (first row) and a zero (second row), respectively. Thus, the adjacent rows are able to check odd and even indices of the code, respectively.

In a further implementation of the second aspect, the {N, K} code and the {N′, K′} code are Hamming codes or Bose-Chaudhuri-Hocquenghem codes.

These codes are particularly good algebraic codes, and moreover perform well with the code construction scheme in example embodiments of the present invention.

In a further implementation of the second aspect, the {N, K} code is a Hamming code with N=127 and K=120, and the {N′, K′} code is a code with N′=128 and K′=119.

For this specific example, the minimum distance of the new code is the same as that of a new code constructed in a conventional manner, but its multiplicity is largely reduced. This significantly decreases error rates under both ML decoding and sub-optimal decoding methods.

In a further implementation of the second aspect, the code generator is included in a device for encoding and/or decoding data based on the {N′, K′ } code.

The device may be an encoder and/or decode, for instance, included in a transmitter, receiver, or transceiver for mobile communications.

A third aspect of the present invention provides a method for constructing an {N′, K′ } code for encoding and/or decoding data transmitted in a communication channel from an {N, K} code, wherein N and N′ are code lengths, K and K′ are code dimensions, and the method comprises shortening the {N, K} code to obtain an intermediate code, and extending the intermediate code to obtain the {N′, K′} code.

In an implementation of the third aspect, N′−N=q>0, K−K′=p>0, and the method comprises shortening the {N, K} code by p positions to obtain an intermediate {N−p, K′} code, and extending the intermediate {N−p, K′} code by p+q positions to obtain the {N′, K′} code.

In a further implementation of the third aspect, the method comprises, for generating the {N′, K′} code from the {N, K} code, modifying a first check matrix that defines the {N, K} code to obtain a second check matrix that defines the {N′, K′} code, the modification of the first check matrix including removing p columns of the first check matrix to obtain a first intermediate matrix, adding {p+q} left or right columns filled with all zeros to the first intermediate matrix to obtain a second intermediate matrix, and adding {p+q} rows to the second intermediate matrix to obtain the second check matrix.

In a further implementation of the third aspect, the method comprises setting {p+q} elements of the left or right {p+q} columns of the second check matrix such that they build an identity matrix.

In a further implementation of the third aspect, the method comprises setting the elements of each of the {p+q} rows of the second check matrix such that it includes alternating ones and zeros.

In a further implementation of the third aspect, the {N, K} code and the {N′, K′} code are Hamming codes or Bose-Chaudhuri-Hocquenghem codes.

In a further implementation of the third aspect, the {N, K} code is a Hamming code with N=127 and K=120, and the {N′, K′} code is a code with N′=128 and K′=119.

In a further implementation of the third aspect, the method is carried out by a device for encoding and/or decoding data based on the {N′, K′} code.

The method of the third aspect and its implementations provide the same advantages and effects as described above for the code generator of the second aspect and its respective implementations.

It has to be noted that all devices, elements, units and means described in the present application could be implemented in the software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be performed by external entities is not reflected in the description of a specific detailed element of that entity which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof.

