WO2021061058A1

WO2021061058A1 - Noise and cyclic redundancy check aided list decoding of error correcting codes

Info

Publication number: WO2021061058A1
Application number: PCT/TR2019/050787
Authority: WO
Inventors: Ahmet Çağrı ARLI; Orhan GAZİ
Original assignee: Cankaya Universitesi
Priority date: 2019-09-23
Filing date: 2019-09-23
Publication date: 2021-04-01

Abstract

The invention relates to Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes that uses forward error correction to enhance bit error rate at the receiver side of any communication system.

Description

NOISE AND CYCLIC REDUNDANCY CHECK AIDED LIST DECODING OF

ERROR CORRECTING CODES

THE TECH N I CAL FI ELD OF THE I NVENTI ON

PRI OR ART ABOUT THE I NVENTI ON(PREVI OUS TECHNI C)

Stochastic Resonance firstly mentioned in [2] and emerges when a weak signal that can’t be detected normally will be detectable after a zero mean white noise is added. Main reason of detection improvement is white noise consists of wide variety of frequencies that resonates with original weak signal frequencies and amplifies the original. Overall signal to noise ratio increases. Using noise as a beneficial phenomena isn’t a new idea. Noise in the scope of stochastic resonance (SR) is proved to be beneficial in weak signal detection (CN107871109, WO2018167476, CN107340055), image processing (CN107343115, CN107292844, US2017287115), target detection (CN107220653, CN106596854), fault diagnosis (CN107084854, CN106706320, CN105938468 ), meat storage time detection (CN104568776, CN104568794, CN104568793), biomedical (CN104951082, US2015126819, CN103494660).

List decoding is proposed by Elias [3] to handle greater number of errors than general error- correcting codes. Motivation of list decoding is outputtin a list of possible messages instead of giving a single possible message. List decoding is shown to be effective especially in Reed- Solomon Codes [4] and successive cancellation list decoders [5] .

The Cylic redundancy check (CRC) was invented in 1961 by W. Wesley Peterson [6] . For example, the 32-bit CRC function used in Ethernet and many other standards since then. CRCs are specifically designed to provide protection against common types of errors in communication channels where the integrity of transmitted messages can be guaranteed quickly and reasonably. A generator polynomial is needed to be specified for CRC code. This polynomial becomes the divisor in the long section of the polynomial, which takes the message as a dividend and where the section is discarded and the remainder. Length of the CRC polynomial is an important parameter about its reliablity. Length should be chosen

1

SUBSTITUTE SHEETS (RULE 26) according to subject data sequence’s length to avoid matching on parity bits of different data sequences.

I n some studies, when and how the artificial noise is introduced in belief propagation based system. Unlike the invention, artificial noise is decided whether to be added or not after a processing. Since belief propagation is an iterative structure then there are older and newer messages through operation. Processing is done by comparing older messages of factor graph with new messages. If any difference is observed then artificial noise is added/injected to that node to overcome oscillating errors.

Al MS OF THE I NVENTI ON AND A BRI EF EXPLAN ATI ON

A new approach for the error correction decoding has been described in the following. Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes is presented in this document. This invention proposed a new approach to error correction decoding with the aid of artificially generated noise intensity and CRC check through the concept of list decoding. Novel approach of the invention is based on using virtually generated noise as an aid to correct errors for further bit error rate performance gain. The most significant advantage of using decoding procedure of the invention is boosting bit error rate (BER) performance. The invention is suitable to be used for all decoding schemes to increase bit error-rate and frame-error-rate performances with a margin of complexity or latency increment. Presented scheme is its generalized structure can be applied to all existing coding schemes from firstly discovered Hamming codes to recently discovered polar codes. The invention combines coding schemes with artificially generated noise from the perpective of list decoding. I n the invention proposed system there is no processing before adding noise into factor graph nodes. Moreover, artificial noise is added to all factor graph nodes in the invention.

One aspect of the invention, CRC check is applied for all L candidates to check whether candidate lead to correct decoding word or not.

Another aspect of the invention, artificial noise is added to all factor graph nodes.

Another aspects of the invention are:

• Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes combines coding schemes with artificially generated noise from the perpective of list decoding. • Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes uses forward error correction to enhance bit error rate.

• CRC check is at each parallel branch of the list decoder.

• Artificially generated noise is produced by additive white Gaussian noise (AWGN) noise generator.

• Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes using virtually generated noise as an aid to correct errors for further bit error rate performance gain.

• Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes can be applied to all existing coding schemes from Hamming codes repetition codes, polynomial codes like BCH nodes, Reed-Solomon codes, Reed-Muller codes, low density parity check codes (LDPC) to recently discovered polar codes.

REFERENCE LI ST

100 Transmitter 101 Data

102 CRC Calculation

103 Encoder

104 Communication Channel

105 Receiver 106 Noise and CRC Aided List Decoder

106a Noise and CRC Aided List Decoder Design A 106b Noise and CRC Aided List Decoder Design B

107 Estimated Data

200 L Parallel Decoders 201 CRC Check

202 Drop Path Notification Box

203 AWGN Noise Generator

300 I ncreasing of Noise Level 301 Check Box

302 Re-transmission Request

THE DESCRI PTI ONS OF THE FI GURE EXPLAI Nl NG THE I NVENTI ON

The figures used to better explain developed with this invention and their descriptions are as follows:

Figure 1. Transmitter and Receiver designs from the perspective of forward error correction

Figure 2. Detailed structure of proposed noise and CRC aided list decoder design A

Figure 3. Detailed structure of proposed noise and CRC aided list decoder design B

Figure 4. BER comparison between BP, SR-BPL+ CRC-16 (L=4), SR-BPL+ CRC-16 (L= 8), SR- BPL+ CRC- 16 (L= 16) and SR-BPL+ CRC-16 (L= 32).

THE DETAI LED EXPLANATI ON OF THE I NVENTI ON

The present invention has been described in detail in the following.

I n this section, a novel of Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes is going to be demonstrated. A proposed invention is based on error correction decoding with the aid of artificially generated noise intensity and CRC check (201 ) through the concept of list decoding.

Shannon’s theorem [1] states that it’s possible to achieve error-free digital information up to a computable maximum rate for any given degree of noise contamination of a communication channel. I n this scope, detection and error correction schemes variety is developed as a sub-branch of coding theory. Schemes are divided into two main groups; block codes and convolutional codes. Block codes are linear such that sum of any two codewords is also a codeword and include Hamming codes, repetition codes, polynomial codes like BCH nodes, Reed-Solomon codes, Reed-Muller codes, low density parity check codes, and polar codes. Besides, convolutional codes make every codeword to be a weighted sum of various input messages and take its names from convolution operation in lineer time invariant systems to find output of a system from input and impulse response. Examples of concolutional systems are punctured convolutional codes and trubo codes. Aim of all mentioned codes is to eliminate effect of noise by using error correction algorithms. Novel approach of the invention is based on using virtually generated noise as an aid to correct errors for further bit error rate performance gain. The invention combines coding schemes with artificially generated noise from the perpective of list decoding. Different noise intensities are applied to different L candidates of decoding stages such that stochastic resonance (SR) occurs so, at least one candidate leads to correct decoding while original received sequence couldn’t be recovered. It is also important to state that artificial noise should be small in power when compared with the communication channel (104) noise. Otherwise, all of the L candidates lead to wrong decoding. As the artificial noise zero mean additive white Gaussian noise (AWGN) is chosen to be used. Cylic redundancy check (CRC) is also a vital component of the invention. CRC is an error detection code commonly used in digital networks and storage devices to detect random changes in raw data. A short control value is assigned to data blocks entering these systems, based on the remainder of the polynomial division of their contents. When retrieving, the calculation is repeated, and if the test values do not match, you can take corrective action against data corruption. CRC check (201 ) is applied for all L candidates to check whether candidate lead to correct decoding word or not.

The invention is suitable to be used for all decoding schemes to increase bit-error-rate and frame-error-rate performances with a margin of complexity or latency increment. I n this scope, two different kind of application of the incention are possible to all block codes and convolutional codes that cares complexity or latency issues caused by list decoding algorithm.

A communication system simply has an transmitter(I OO), a communication channel (104) and a receiver (105) as seen in Fig .1 . Since the invention is about error correction codes, the invention demonstration of a communication channel (104) excludes modulation and RF chain blocks for a simple understanding. Proposed design starts in transmitter (100) with user data (101 ) generation. CRC calculation (102) is done and parity bits are added to data (101 ) sequence. After this step, encoder (103), block simply multiplies data (101 ) sequence with generator matrix G_N where N is CRC parity added data (101 ) sequence length. Encoded data (101 ) sequence is sent to receiver (105), through communication channel (104). Proposed design starts with receiver (105) and received data (101 ) is decoded in Noise and CRC aided List decoder (106). As a result, estimated data (107) is obtained.

As mentioned before there are two different verisons of proposed Noise and CRC aided List decoder (106) named as Noise and CRC Aided List Decoder Design A (106a) and Noise and CRC Aided List Decoder Design B (106b). Fig.2 shows a more detailed block diagram of Noise and CRC Aided List Decoder Design A (106a). I n fig.2, number of L parallel decoders (200) depends on number of L. Number of AWGN noise generator (203) goes on until number of L-1 and starts with second L parallel decoders (200). Number of CRC check (201 ) depends on number of L. Number of CRC check (201 ) goes on until number of L.Noise and CRC aided list decoder of design A (106a) consists of L parallel decoders (200), (of any code), AWGN noise generator (203) which is for generation of artificial noise, and a CRC check (201 ) block, where L is list size. Each AWGN noise generator (203) produces different noise intensities and added to the communication channel (104) output. There should be L-1 different AWGN noise generator (203) to be able to produce noise intensities at different power levels. At each parallel branch of the list decoder CRC check (201 ) is done. The path that doesn’t satisfy CRC check (201 ) is dropped in Drop path notification box (202). At the end, estimated data (107) is selected among the decoded sequences that pass CRC check (201 ) .

Similarly, Fig.3 focuses on Noise and CRC Aided List Decoder Design B (106b). I n Fig.3, symbol i indicates current decoding stage i starts from 1 and goes until list size L if decoding fail at every stage oise and CRC Aided List Decoder Design B (106b) focuses on complexity reduction such that one decoder, L parallel decoders (200), works until a CRC check (201 ) is satisfied. A check box (301 ) checks whether times proposed decoding structure worked L times or not. Otherwise a re-transmission request (302), takes place. If CRC check (201 ) is satisfied then estimated codeword, estimated data (107) can be acheived. It’s also important to state that at each decoding loop noise level is increased (I ncreasing of Noise Level (300) state), to be able to find stochastic resonance point of the decoder of any code and estimated transmitted data (101 ).

Artificial noise intesity and CRC check (201 ) code length can be varying for different coding schemes, communication channel (104) model, code rate. Thus must be decided by needs of the communication protocol. The most significant advantage of using decoding procedure of the invention is boosting bit error rate (BER) performance. Another feature of presented scheme is its generalized structure can be applied to all existing coding schemes from firstly discovered Hamming codes to recently discovered polar codes [7]

Fig. 4 shows the BER performance of artificial noise and CRC-16 aided belief propagation based list (BPL) decoding of polar codes P(2048,1024) under Binary Phase Shift Keying (BPSK) modulation over AWGN channel. Artificial noise standard deviation is changed between 0 to 0.4 with steps of 0.0125. It can be observed from the Fig.4 that as the list size increases BER gain of corresponding coding scheme also increases. SR-BPL+ CRC-16 (Stochastic Resonance and CRC aided based Belief Propagation List Polar Decoder) states for our method that is applied to the polar codes. System of the invention is subject to receiver (105) side of any communication system that uses forward error correction to enhance bit error rate. Adding of an artificial noise for each branch and it’s usage in forward error correction is new. Operation steps can be defined as below.

From the above detailed description, the method of Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes which is suitable to be used for all decoding schemes to increase bit-error-rate and frame-error-rate performances with a margin of complexity or latency increment comprising the steps of;

At the receiver (105) side of any communication system;

• Setting of L (user defined) parallel branches which is in decoders,

• Adding of an artificially generated noise for each branch with different noise level to each branch of the system,

• Performing of Decoding,

• Checking of Cylic redundancy check (CRC) to check whether successful decoding is performed or not in each branch,

• Controlling of output of the branch with Cylic redundancy check (CRC) check (201 ),

• If output of the branch with Cylic redundancy check (CRC) check (201 ) is satisfied, It is assumed to be successful then,

• Ending of Decoding.

REFERENCES

[1] C. E. Shannon, "A mathematical theory of communication," in The Bell System Technical Journal, vol. 27, no. 3, pp. 379-423, July 1948.

[2] R. Benzi, A. Sutera, and A. Vulpiani, “The mechanism of stochastic resonance,” J. Phys. A. Math. Gen., vol. 14, no. 11 , pp. L453-L457, Nov.1981.

[3] P. Elias, "Error-correcting codes for list decoding," in I EEE Transactions on I nformation Theory, vol. 37, no. 1 , pp. 5-12, Jan. 1991.

[4] R. Koetter, J. Ma and A. Vardy, "The Re-Encoding Transformation in Algebraic List- Decoding of Reed-Solomon Codes," in I EEE Transactions on I nformation Theory, vol. 57, no. 2, pp. 633-647, Feb. 2011.

[5] I . Tal and A. Vardy, "List decoding of polar codes,” in Proc. of I EEE I nt. Symp. on I nf. Theory,, 2011 , pp. 15.

[6] Peterson, W. W.; Brown, D. T. (January 1961 ). "Cyclic Codes for Error Detection". Proceedings of the I RE. 49 (1 ) : 228-235. [7] E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-I nput Memoryless Channels,” l EEE Trans. I nf. Theory, vol. 55, no. 7, pp. 3051-3073, Jul. 2009.

Claims

CLAI MS

1 . The method of Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes for all decoding schemes to increase bit-error-rate and frame-error- rate performances with a margin of complexity or latency increment, characterized in comprising the steps of;

At the receiver (105) side of any communication system;

• Setting of L (user defined) parallel branches which is in decoders,

• Performing of Decoding,

• Controlling of output of the branch with Cylic redundancy check (CRC) check

(201 ) ,

• Ending of Decoding.

2. The method of according to claim 1 ; wherein CRC check (201 ) is applied for all L candidates to check whether candidate lead to correct decoding word or not.

3. The method of according to claim 1 ; wherein artificial noise is added to all factor graph nodes.

4. The method of according to claim 1 ; wherein Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes combines coding schemes with artificially generated noise from the perpective of list decoding.

5. The method of according to claim 1 ; wherein Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes uses forward error correction to enhance bit error rate.

6. The method of according to claim 1 ; wherein CRC check (201 ) is at each parallel branch of the list decoder.

7. The method of according to claim 1 ; wherein artificially generated noise is produced by additive white Gaussian noise (AWGN) noise generator (203).

8. The method of according to claim 1 ; wherein Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes using virtually generated noise as an aid to correct errors for further bit error rate performance gain.

9. The method of according to claim 1 ; wherein Noise and Cyclic Redundancy Check aided List Decoding of Error Correcting Codes can be applied to all existing coding schemes from Hamming codes repetition codes, polynomial codes like BCH nodes, Reed-Solomon codes, Reed-Muller codes, low density parity check codes (LDPC) to polar codes.