Kaykac Egilmez, Zeynep · ePrints Soton (University of Southampton) · 2022
Arikan's polar codes offer near-capacity error correction performance across a wide range of block lengths, as well as coding rates. The standardization of polar codes by the Third Generation Partnership Project (3GPP) 5th Generation (5G) New Radio (NR) in 2016, significantly increased the interest in polar codes. In particular, polar codes have been adopted by the 3GPP SG NR, since they provide near-capacity error correction for the short control messages transmitted in the control channels of the 3GPP SG NR, where other state-of-the-art channel decoders have struggled. The state-of-the-art Soft-Input Hard-Output (SIHO) Successive Cancellation List (SCL) and Cyclic Redundancy Check-Aided SCL (CA-SCL) polar decoders offer the best hard-decision performance among the polar decoders but they do not have a soft-output capability, which is necessary for achieving iterative gains in turbo-detection or in Joint Source Channel Coding (JSCC). Hence, there is a distinct knowledge-gap concerning Soft-Input Soft-Output (SISO) polar decoders capable of outperforming the well-known SISO Belief Propagation (BP), the Soft Cancellation (SCAN) polar decoders, as well as that of the hard-decision SCL polar decoder. Against this background, a pair of novel SISO polar decoding algorithms are proposed, which outperform both the SISO BP and SCAN polar decoders, as well as the state-of-the-art SCL polar decoder across a wide range of block lengths and coding rates. Additionally, both the error correction and error detection performance of these novel polar codes are characterised. More specifically, a two-stage serially concatenated scheme of polar codes exchanging extrinsic information with an inner decoder is conceived. Explicitly, the first stage comprising a SG NR polar decoder, and a second stage comprising a turbo-detected 2x2 Multiple Input Multiple Output (MIMO)-aided scheme is designed, by proposing a novel SISO G-SCAN polar decoding scheme. The G-SCAN decoding scheme advocated offers the best of both worlds by generating soft outputs for achieving iterative decoding gains, and hard outputs that improve the SCL decoding performance. Furthermore, the Two-Dimensional (2D) Extrinsic Information Transfer (EXIT) chart analysis of this two-stage serially concatenated scheme is carried out. Furthermore, a three-stage serially concatenated scheme is designed, which exchanges extrinsic soft information between the polar decoder as well as an inner and outer decoder. Explicitly, the first stage is a JSCC scheme, the second stage is a 5G NR polar decoder, and the third stage is a 2x2 MIMO scheme, which is investigated. Additionally, a novel hybrid polar decoder algorithm is proposed, which is capable of generating soft outputs for iterative extrinsic information exchange with an inner and outer decoder. Finally, a Three-Dimensional (3D) EXIT chart analysis of SISO polar codes is provided for the first time.
Cited by 0
Liudmila Karakchieva, Peter Trifonov · IEEE Transactions on Communications · 2023
A reduced complexity symbolwise maximum a posteriori probability (MAP) decoding algorithm for linear block codes is presented. This algorithm is based on the recursive trellises and performs two passes over the recursion tree. Probability-domain and Log-Max implementations are considered. Numeric results show that the proposed method has lower complexity compared to other known recursive algorithms and the classical BCJR algorithm. The complexity analysis for random codes is provided.
Cited by 1
Philippa A. Martin, D.P. Taylor, M.P.C. Fossorier · 2003
List-based SISO decoding algorithms calculate extrinsic information using a list of codewords. They try to produce a list containing the closest codewords to the soft input by encoding or decoding test sequences. Ideally for each position in the code, there is at least one codeword in the list with a '1' in that position and at least one with a '0'. The extrinsic information must be estimated in positions where there is not. We focus on encoding-based algorithms since they retain performance as the minimum Hamming distance of the code, d/sub H,min/, increases, whereas, decoding-based algorithms generally become increasingly inefficient. We consider product codes with extended BCH component codes. They are transmitted using BPSK over a memoryless additive white Gaussian noise channel. The proposed algorithm can easily be extended to different channel models, modulation schemes and concatenated codes.
Cited by 4
Philippa A. Martin, A. Valembois, M.P.C. Fossorier et al. · IEEE Transactions on Communications · 2004
The box and match decoding algorithm (BMA) significantly reduces the computational complexity of the ordered statistic decoding algorithm at the expense of increased memory requirements. A soft-input/soft-output version of the BMA is developed. Additional complexity-reduction techniques are also described.
Cited by 7
Carlo Condo · 2022 IEEE Globecom Workshops (GC Wkshps) · 2022
Guessing Random Additive Noise Decoding (GRAND) is a universal decoding algorithm that can be used to perform maximum likelihood decoding. It attempts to find the errors introduced by the channel by generating a sequence of possible error vectors in order of likelihood of occurrence and applying them to the received vector. Ordered reliability bits GRAND (ORBGRAND) integrates soft information received from the channel to refine the error vector sequence. In this work, ORBGRAND is modified to produce a soft output, to enable its use as an iterative soft-input soft-output (SISO) decoder. Three techniques specific to iterative GRAND-based decoding are then proposed to improve the error-correction performance and decrease computational complexity and latency. Using the OFEC code as a case study, the proposed techniques are evaluated, yielding substantial performance gain and astounding complexity reduction of 48% to 85% with respect to the baseline SISO ORBGRAND.
Cited by 18
Yali Liu, Jiangtao Wen · 2004
The paper described an optimal search based and a heuristic search based decoding algorithm for arithmetic codes and compared their performance and complexity with the traditional "hard" bit based AC decoder. To approach a different error resilient AC decoding, a heuristic search algorithms (HSAs) in artificial intelligence for finding the minimal-weight path through directed and nonnegatively-weighted graphs is utilized when the bitstream is transmitted over error prone channels. Simulation results showed that both algorithms easily outperformed traditional "hard" bits based arithmetic decoder, while the heuristic search based algorithm achieved a very good tradeoff between performance and complexity.
Cited by 1
Konstantinos Nikitopoulos, Dan Zhang, I‐Wei Lai et al. · IEEE Communications Letters · 2010
In this paper two complexity efficient soft sphere-decoder modifications are proposed for computing the max-log LLR values in iterative MIMO systems, which avoid the costly, typically needed, full enumeration and sorting (FES) procedure during the tree traversal without compromising the max-log performance. It is shown that despite the resulting increase in the number of expanded nodes, they can be more computationally efficient than the typical soft sphere decoders by avoiding the unnecessary complexity of FES.
Cited by 16Open access
Benedetto, S., Divsalar, D., Montorsi, Guido et al. · PORTO Publications Open Repository TOrino (Politecnico di Torino) · 1997
Cited by 0
He Wang, Sunghwan Kim · IEEE Photonics Technology Letters · 2015
In this letter, we propose a new decoding algorithm based on a soft-input soft-output run-length limited (RLL) decoder in visible light communication (VLC) with on-off keying (OOK) modulation and Reed-Solomon (RS) codes. Conventional RLL codes are used for dimming adjustments in VLC; however, in our receiver model, the posterior probability matrix is produced by the new RLL decoder, and it can be matched as the input of the soft RS decoder to enhance the throughput in the VLC system. A significant advantage of our proposed method is that it leads to the enhancement of bit error rate (BER) and frame error rate (FER) performances without any change in the transmitter in VLC systems. The simulation results show that the majority of the BER and FER performances of our proposed method are better than those of hard-input hard-output RLL decoding and soft-input hard-output RLL decoding methods.
Cited by 21
Yali Liu, Jiangtao Wen · 2013
Arithmetic coding for data compression has gained widespread acceptance for optimum compression when used in a suitable model. The "traditional " hard bit based decoding suffers from severe loss of data when errors are present in the received bitstream. In this paper, heuristic-search based algorithms are introduced for the decoding of arithmetic coded bitstreams. They utilize both channel "soft " bit reliability information and synchronization and number of symbols information to identify the most likely sequence of source symbols received. Key words: heuristic search, arithmetic coding, soft-decoding 1.
Cited by 0
Jing Jiang, Krishna R. Narayanan · 2006
An iterative algorithm is presented for soft-input-soft-output (SISO) decoding of Reed-Solomon (RS) codes. The proposed iterative algorithm uses the sum product algorithm (SPA) in conjunction with a binary parity check matrix of the RS code. The novelty is in reducing a submatrix of the binary parity check matrix that corresponds to less reliable bits to a sparse nature before the SPA is applied at each iteration. The proposed algorithm can be geometrically interpreted as a two-stage gradient descent with an adaptive potential function. This adaptive procedure is crucial to the convergence behavior of the gradient descent algorithm and, therefore, significantly improves the performance. Simulation results show that the proposed decoding algorithm and its variations provide significant gain over hard decision decoding (HDD) and compare favorably with other popular soft decision decoding methods.
Cited by 0
Ernst Martin Witte, Gerd Ascheid · RWTH Publications (RWTH Aachen) · 2012
In the past decades, improved algorithms and more densely integrated circuits enabled rapid progress in the area of mobile communications. The fast proliferation of mobile multimedia content and the exponentially increasing data rates demand for more and more efficient wireless transmission principles and receivers. An approach called "MIMO" (multiple input, multiple output) improves the spectral efficiency by transmitting multiple data streams concurrently within the same bandwidth by using multiple transmit and receive antennas. This approach is already part of several mobile communication standards such as LTE, WLAN and HSPA. Aside from an increasing efficiency, mobile receivers need to support a rapidly growing number of communication standards as well as updates after fabrication. Therefore, the trend towards flexibility is also relevant for physical layer receiver architectures. However, flexibility causes costs (e.g. in terms of chip area or energy consumption) which can be orders of magnitude higher than for application specific integrated circuits. In the context of this thesis, efficiency and flexibility aspects have been investigated for "Sphere-Decoding" (SD), an important class of MIMO receiver algorithms. By iterative feedback of bitwise reliability information ("soft-input soft-output", SISO) between the MIMO demodulator and the channel decoder, a spectral efficiency near the theoretical limits can be achieved. The algorithmic basis for SISO SD is well known for some time. However, due to the high complexity of SISO SD, up to the beginning of this work only architectures existed which support the non-iterative soft-output SD. The first SISO SD architecture has been developed in the context of this thesis. It provides a high efficiency with a limited flexibility which allows switching antenna and modulation configurations at runtime. Beyond this architecture, SISO SD implementations for representative programmable architectures have been investigated. The resulting analysis provides an important insight into the trade-offs between efficiency, flexibility and portability of this class of algorithms. Such iterative demodulation/decoding architectures cannot be compared by single points of operations due to their inherent trade-off between complexity and spectral efficiency. Therefore, a special analysis approach has been elaborated as part of this work which enables comparisons under preferably identical scenarios (error rates, throughput latency and chip area). This approach enables reasonable and fair comparisons of complexity, efficiency and flexibility of very different architectures. Based on these analyses, points of operation can be estimated which allow an economic use of SISO-SD architectures in future mobile receivers.
Cited by 3Open access
Dan Zhang, I‐Wei Lai, Gerd Ascheid · 2011
For soft-input soft-output sphere decoding (SD), the combination of the Schnorr-Euchner (SE) enumeration and the radius reduction shrink the search space quickly but with considerable computational complexity. In this paper, a low complexity approach is proposed to reduce the tree search space before SD starts. Particularly, such reduction is achieved by 1) tightening the initial radius; 2) restricting the search space to a subset of the symbol lattice. With further enhancement on the tree pruning constraint, simulation results demonstrate significant complexity savings with negligible error rate performance loss.
Cited by 0
Witte, Ernst Martin, Borlenghi, Filippo, Ascheid, Gerd et al. · RWTH Publications (RWTH Aachen) · 2010
Cited by 0
Yuval Genga, Olutayo O. Oyerinde, D.J.J. Versfeld · SAIEE Africa Research Journal · 2021
In this paper, a bit-level decoder is presented for soft-input soft-output iterative decoding of Reed-Solomon (RS) codes. The main aim for the development of the proposed algorithm is to reduce the complexity of the decoding process, while yielding a relatively good error correction performance, for the efficient use of RS codes. The decoder utilises information set decoding techniques to reduce the computational complexity cost by lowering the iterative convergence rate during the decoding process. As opposed to most iterative bit-level soft-decision decoders for RS codes, the proposed algorithm is also able to avoid the use of belief propagation in the iterative decoding of the soft bit information, which also contributes to the reduction in the computational complexity cost of the decoding process. The performance of the proposed decoder is investigated when applied to short RS codes. The error correction simulations show the proposed algorithm is able to yield a similar performance to that of the Adaptive Belief Propagation (ABP) algorithm, while being a less complex decoder.
Cited by 2Open access
Sergio Benedetto, G. Montorsi, D. Divsalar et al. · European Transactions on Telecommunications · 1998
Abstract Soft‐input soft‐output building blocks (modules) are presented to construct and iteratively decode in a distributed fashion code networks , a new çoncept that includes, and generalizes, various forms of concatenated coding schemes. Among the modules, a central role is played by the SISO module (and the underlying algorithm): it consists of a four‐port device performing a processing of the sequences of two input probability distributions by constraining them to the code trellis structure. The SISO and other soft‐input soft‐output modules are employed to construct and decode a variety of code networks, including “turbo codes” and serially concatenated codes with interleavers.
Cited by 223
Jiang Ji, Krishna R. Narayanan · IEEE Transactions on Information Theory · 2006
An iterative algorithm is presented for soft-input soft-output (SISO) decoding of Reed-Solomon (RS) codes. The proposed iterative algorithm uses the sum-product algorithm (SPA) in conjunction with a binary parity-check matrix of the RS code. The novelty is in reducing a submatrix of the binary parity-check matrix that corresponds to less reliable bits to a sparse nature before the SPA is applied at each iteration. The proposed algorithm can be geometrically interpreted as a two-stage gradient descent with an adaptive potential function. This adaptive procedure is crucial to the convergence behavior of the gradient descent algorithm and, therefore, significantly improves the performance. Simulation results show that the proposed decoding algorithm and its variations provide significant gain over hard-decision decoding (HDD) and compare favorably with other popular soft-decision decoding methods
Cited by 178
Mao‐Ching Chiu · 2003
The optimal decoding scheme for asynchronous code-division multiple access (CDMA) systems that employ convolutional codes results in a prohibitive computational complexity. To reduce computational complexity, iterative receiver structures have been proposed for decoding multiuser data. At each iteration, extrinsic information is exchanged between a soft-input/soft-output (SISO) multiuser detector (MUD) and a bank of single-user SISO channel decoders. For asynchronous cases (see Alexander, P.D. et al., IEEE Trans. Commun., vol.47, p.1008-14, 1999), an optimal SISO MUD was derived based on the chip-synchronous assumption which is in general not valid for asynchronous CDMA systems. We propose an algorithm for an optimal SISO MUD without the chip-synchronous assumption. A direct implementation of the optimal SISO MUD also has exponential computational complexity in terms of the number of users, which is still prohibitive for channels with medium to large numbers of users. A low-complexity SISO MUD is proposed based on the decision-feedback scheme. In it, tentative hard decisions are made and fed back to the SISO multiuser from previously decoded output. The computational complexity of this detector can be linear in terms of the number of users and can be adjusted according to the complexity/performance trade-off. Simulations show that the performance of the low-complexity SISO MUD approaches that of the single-user system for moderate to high signal-to-noise ratios (SNR), even for a large number of users.
Cited by 0
Zeynep B. Kaykac Egilmez, Luping Xiang, Robert G. Maunder et al. · IEEE Transactions on Vehicular Technology · 2022
Soft-Input Soft-Output (SISO) polar decoding algorithms, such as Belief Propagation (BP) and Soft Cancellation (SCAN) polar decoding, offer iteration capability for facilitating turbo-style detection. However, at lower Signal-to-Noise Ratios (SNRs), the performance of the BP and SCAN decoders is about 1.5 dB and 0.5 dB worse than that of the state-of-the-art hard-decision Successive Cancellation List (SCL) decoding algorithm, respectively, despite iteratively exchanging information with a Multiple Input Multiple Output (MIMO) detector. Motivated by this gap, we conceive a novel G-SCAN polar decoder, which generates both soft-decision and hard-decision outputs. This is achieved by intrinsically amalgamating a list decoder with a novel SISO decoder. These soft-decision outputs may be used for turbo-detection, but they also support the hard-decision outputs of the SCL algorithm for achieving superior block error rate (BLER) performance. As a result of these benefits, the proposed G-SCAN algorithm using a list size of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L = 2$</tex-math></inline-formula> offers around 1 dB BLER gain compared to the conventional hard-decision SCL decoder relying on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$L = 32$</tex-math></inline-formula> . Furthermore, we have carried out its Extrinsic Information Transfer (EXIT) chart analysis, and characterized the performance vs. the complexity of the proposed G-SCAN algorithm, and compared it to various soft- and hard-decision output benchmarks for a wide variety of different rate-matching modes and block lengths. Furthermore, in order to reduce the complexity of the proposed algorithm, a novel Cyclic Redundancy Check (CRC)-aided G-SCAN algorithm is also proposed, which facilitates early termination and improves the BLER performance.
Cited by 18
Hitoshi Tokushige, Jun Asatani, M.P.C. Fossorier et al. · Birkhäuser Basel eBooks · 2004
In this paper, we consider a soft-input and soft-output iterative bounded-distance decoding (SISO-IBDD) algorithm in which the bounded-distance decodings are performed sequentially. And we study a computation method of a soft-output value to approximate Max-Log-MAP. In the decoding algorithm, search centers are generated by the sums of the hard-decision sequence obtained from a received sequence and test patterns which are selected beforehand, and the bounded-distance decodings with respect to the search centers are performed. We have proposed a selection method of test patterns for an iterative bounded-distance decoding (IBDD) algorithm in [5]. Simulation results have shown that the IBDD algorithm whose test patterns are selected by the proposed method with considerably small number of iterations provides better error performance than the Chase II decoding algorithm for several BCH codes over an AWGN channel using BPSK signaling. We adopt the selection method of test patterns for the SISO-IBDD algorithm and a computation method of a soft-output value which is modified based on the proposed method in [2] with respect to reliability factors. Over the AWGN channel using the BPSK signaling, we show bit error rates and average soft-output values given by the SISO-IBDD algorithm for the extended BCH (64, 36, 12) and (64, 45, 8) codes by computer simulation. For the extended BCH codes, the simulation results show that bit error rates of the SISO-IBDD algorithm are relatively smaller than those of a Chase-like decoding algorithm with the same number of iterations of the bounded-distance decodings and for each component bit, average soft-output values provided by the SISO-IBDD algorithm are close to those by the Max-Log-MAP decoding algorithm by computer simulation.
Cited by 0