Decoding Algorithm by Cooperation Between Hartmann Rudolph Algorithm and a Decoder Based on Syndrome and Hash

Decoding Algorithm by Cooperation Between Hartmann Rudolph Algorithm and a Decoder Based on Syndrome and Hash

My Seddiq El Kasmi Alaoui, Said Nouh
Copyright: © 2021 |Pages: 13
DOI: 10.4018/IJNCR.2021010102
(Individual Articles)
No Current Special Offers


In this paper, the authors present a concatenation of Hartmann and Rudolph (HR) partially exploited and a decoder based on hash techniques and syndrome calculation to decode linear block codes. This work consists firstly to use the HR with a reduced number of codewords of the dual code then the HWDec which exploits the output of the HR partially exploited. Researchers have applied the proposed decoder to decode some Bose, Chaudhuri, and Hocquenghem (BCH) and quadratic residue (QR) codes. The simulation and comparison results show that the proposed decoder guarantees very good performances, compared to several competitors, with a much-reduced number of codewords of the dual code. For example, for the BCH(31, 16, 7) code, the good results found are based only on 3.66% of the all codewords of the dual code space, for the same code the reduction rate of the run time varies between 78% and 90% comparing to the use of Hartmann and Rudolph alone. This shows the efficiency, the rapidity, and the reduction of the memory space necessary for the proposed concatenation.
Article Preview

1. Introduction

Given that digital communication has become increasingly important, the volume of data exchanged is growing continuously and the communication channels are not entirely reliable so the need to ensure the reliability of the transmitted data to the reception is a pivotal process; hence channel coding has become an indispensable means for detecting and correcting errors on computer networks, telecommunication systems and data storage. A variety of error correcting codes are implemented in diverse devices such as Smartphones, compact discs (CDs), digital versatile discs (DVDs), hard disks or packets transferred over Interconnected Network (Internet) or over mobile networks. Given the difficulty of the problem, several linear code decoding algorithms are used to improve the measured performance as a function of bit error rate (BER).

Decoding algorithms employed in communication systems are classified into two principal categories: soft decision and hard decision algorithms. Soft decision algorithms exploit directly the received symbols and they employ principally the Euclidian distance as a measure to minimize the distance. On the other hand, hard decision algorithms work on binary inputs that result from thresholding of the transmit channel output. This type of algorithms usually use the Hamming distance as a metric(Clarck & Cain, 1981). Among the works that are interested in the hard decision algorithms, we find these based on the genetic algorithms (GA) (Azouaoui et al., 2012), (Gallager, 1962), (Morelos-Zaragoza, 2006), (Nouh, 2012), the algebraic decoder (Berlekamp, 1984), (Massey, 1969), (Chen et al., 2007) of Berlekamp-Massey based on compute of syndromes and it has an efficient mechanism to localize all corrigible errors. We also find some works based on syndrome decoding and the hash techniques (Chen et al., 2016), (El Kasmi Alaoui et al., 2019c), for example in (El Kasmi Alaoui et al., 2019c), the researchers have presented two fast and efficient decoders, HSDec(hard decision decoder based on Hash and Syndrome Decoding) and HWDec(Hard decision decoder based on the error Weight Decreasing).

For soft decision decoders, we find an algorithm applicable for BCH codes based on test and syndrome computing to localize the error positions (Jung et al., 2016). Askali et al. have presented a version Soft In-Hard Out (SIHO) where they have used the MacWilliams’s permutation decoding algorithm (McPD) as a hard decoder (Askali, 2012). To facilitate self-synchronization of the digital communication systems Shim et al. have proposed a forward error correction codes in communication channels (Shim, 2017). In (Berkani et al., 2017) a compact Genetic Algorithms (cGA) is used to generate two dual domain Soft Decision decoders. The low complexity of the HSDec algorithm compared with its competitors encouraged us to combine it with the Chase-2 algorithm (El Kasmi Alaoui et al., 2017). In (Fossorier & Lin, 1995), Fossorier et al. have presented the OSD (Ordered Statistics Decoder) algorithm which is based on ordered statistics and it’s applicable on linear block codes. A decoding algorithm which principle is different to those cited above, is which presented by Hartmann and Rudolph (HR) in (Hartmann & Rudolph, 1976). The main idea behind this decoder is the symbol by symbol decoding of the received sequence. In (El Kasmi Alaoui et al., 2020; El Kasmi Alaoui et al., 2019a; El Kasmi Alaoui et al., 2019b; Nouh, 2018), several decoders developed from a serial concatenation are presented.

In (El Kasmi Alaoui et al., 2019a), we have presented a serial concatenation between Hartmann & Rudolph partially exploited and HSDec decoder that is based on hash techniques and syndrome calculation. The main idea in HSDec decoder is based on a hash function that permits to find the error pattern directly from the syndrome of the received word. The storage position of each corrigible error pattern is equal to the decimal value of its syndrome and therefore the time complexity is much reduced comparing to known low complexity decoders. The main disadvantage of HSDec is its spatial complexity, because it requires to previously storing all corrigible error patterns in memory. To solve this problem, we propose to replace HSDec by HWDec decoder that is based also on hash techniques and syndrome calculation, but it requires storing only the weight of each corrigible error pattern instead of the error pattern itself.

Complete Article List

Search this Journal:
Volume 12: 1 Issue (2024): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2021)
Volume 9: 4 Issues (2020)
Volume 8: 4 Issues (2019)
Volume 7: 4 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing