Zhenhua Xie, C.K. Rushforth · 2003
The authors consider the application of sequential decoding to the detection of data transmitted on an additive white Gaussian noise channel by K asynchronous transmitters using direct-sequence spread-spectrum multiple-access (DS/SSMA). They described a modification of R.M. Fano's (1963) sequential decoding metric, and evaluate by computer simulation the performance of a sequential decoder that uses this modified metric in conjunction with the stack algorithm. It is concluded that, in many circumstances, the sequential decoder achieves results comparable to those obtained using the much more complicated optimal receiver. It is concluded that the decoder considered would appear to offer an attractive tradeoff between complexity and performance in many cases of interest.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 15
Mohsen Moradi, Salman Habib, Vahid Nourozi et al. · arXiv (Cornell University) · 2026
Quantum low-density parity-check (QLDPC) codes are a leading approach to quantum error correction, yet conventional belief propagation (BP) decoders often perform poorly, primarily due to non-convergence exacerbated by stabilizer constraints, which induce short cycles and degeneracy. We propose two scheduling variants, sequential check node scheduling (SCNS) and sequential variable node scheduling (SVNS), that improve BP's error-correction ability by processing check nodes (CNs) or variable nodes (VNs), respectively, in a fixed order, stabilizing message updates and reducing stalls. We also employ this technique to an improved BP-variant called BP guided decimation (BPGD), where symbols are progressively fixed during decoding iterations. Here, we demonstrate that the sequential BPGD (SBPGD) decoder can further improve the convergence properties and performance of the decoder. On standard QLDPC benchmarks under a Pauli-X noise model, our sequential schedules are shown to lower the block error rate relative to conventional BP, and SBPGD outperforms BPGD while using significantly fewer decimation rounds, translating to lower computational cost. These results demonstrate that changing the update schedule, without altering the code, can improve both the reliability and efficiency of BP-based decoding for QLDPC codes. For the [[1922,50,16]] C2 hypergraph-product code with independent X errors, SVNS-BP surpasses BP-OSD-0 in error correction at roughly the same complexity as standard BP.
Cited by 0Open access
Johannesson, Rolf, Sidorenko, Vladimir, Kamil Sh. Zigangirov · Lund University Publications (Lund University) · 1988
It is well known that the computational performance of sequential decoding deteriorates greatly when channel errors occur in clusters, as in Gilbert channels. A way of using sequential decoding to exploit the memory of a Gilbert channel that alleviates this problem is presented. A Fano-like metric matched to this channel is used. The method is investigated by simulating sequential decoding utilizing the stack algorithm. The simulations confirm the feasibility of the technique.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 2Open access
Kallel, Samir, Haccoun, David · PolyPublie (École Polytechnique de Montréal) · 1985
Cited by 0
James L. Massey, Michael K. Sain, J. Geist · Discrete Mathematics · 1972
Cited by 10
Rein Teoste · 1969
Cited by 2
Hermano A. Cabral, Daniel J. Costello, Jr. · 2007
This paper investigates the extension of the BHD scheme to TCM, in particular to 8-PSK and 16-QAM constellations. The BHD algorithm is modied and simulations results are presented which show about a 1dB coding gain compared to ordinary sequential decoding. We also compare the BHD/TCM scheme with turbo TCM (TTCM) schemes, which employ turbo codes as the underlying code in TCM[4].
Cited by 0
A. Drukarev, Daniel J. Costello · IEEE Transactions on Information Theory · 1983
An important feature of ARQ sequential decoding is that a very low undetected error probability can be achieved without increasing significantly the complexity of decoding. Several ARQ sequential decoding algorithms based on the stack algorithm are considered. Analysis is done for a memoryless channel with noiseless feedback, and the emphasis is on evaluating the undetected error probability and the maximum throughput attainable with each algorithm. A time-out algorithm is analyzed and the parameters optimizing the performance of this algorithm are found. A new algorithm called the slope control algorithm, capable of achieving a better throughput than the time-out algorithm, is proposed. The algorithm is analyzed using random coding arguments, and the parameters maximizing the throughput for various conditions are found. All theoretical results are verified by computer simulation for a binary symmetric channel.
Cited by 61
M. Cedervall, Rolf Johannesson, Kamil Sh. Zigangirov · Lund University Publications (Lund University) · 1985
Cited by 2
Samir Kallel, David Haccoun · 1987
In this paper we consider sequential decoding with ARQ and code combining under the time-out condition. That is whenever the decoding time of a given packet exceeds some predetermined duration, decoding is stopped and retransmission of the packet is requested. However the unsuccessfull packets are not discarded, but are combined with their retransmitted copies. We show that the use of code combining allows sequential decoding to operate efficiently even when the coding rate R exceeds the computational cut-off rate R <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">como</inf> . Furthermore, an analysis of the Ideal-Selective-Repeat ARQ scheme shows that the use of code combining yields a significant throughput even at very high channel error rates, thus making it a very robust hybrid FEC/ARQ system.
Cited by 12
Yibin Ng, Wai Ho Mow · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 1998
Cited by 0
B. Narayanaswamy, Yaron Rachlin, Rohit Negi et al. · 2009
Cited by 0
Ran Xu, Taşkın Koçak, Graeme Woodward et al. · Explore Bristol Research · 2009
Various techniques, such as bidirectional search, have been employed in sequential decoding to reduce the decoding delay. In this paper, a bidirectional Fano algorithm (BFA) is proposed, in which a forward decoder (FD) and a backward decoder (BD) search in the opposite direction simultaneously. It is shown that the proposed BFA can reduce the average decoding delay by at least 50% compared to the unidirectional Fano algorithm (UFA). Due to the reduction in the variability of the computational effort by using bidirectional search, there is even higher decoding throughput improvement at low signal-to-noise-ratio (SNR). For example at Eb/No=3dB, there is 300% throughput improvement by using the BFA decoding compared to the conventional UFA decoding. The proposed BFA decoding technique can be employed in very high throughput wireless communication systems with low hardware complexity and power consumption.
Cited by 10Open access
Melnik Ivan, Kalygin Georgy, Kulikov Konstantin · Lecture notes in networks and systems · 2024
Cited by 0
Anisha Banerjee, Andreas Lenz, Antonia Wachter-Zeh · IEEE Transactions on Communications · 2024
Sequential decoding, commonly applied to substitution channels, is a sub-optimal alternative to Viterbi decoding with significantly reduced memory costs. This work describes and analyzes a sequential decoder for convolutional codes over channels prone to insertion, deletion, and substitution errors. Our decoder expands the code trellis by a new channel-state variable, called drift state, as proposed by Davey and MacKay. A suitable decoding metric on that trellis for sequential decoding is derived, generalizing the original Fano metric. The decoder is also extended to facilitate the simultaneous decoding of multiple received sequences that arise from a single transmitted sequence. Under low-noise environments, our decoding approach reduces the decoding complexity by multiple orders of magnitude compared to Viterbi’s algorithm, albeit at slightly higher bit error rates. An analytical method to determine the computational cutoff rate is also suggested. This analysis is supported by numerical evaluations of bit error rates and computational complexity, compared to optimal Viterbi decoding.
Cited by 3Open access
Yunning Zhong, Ping Xu, Siming Zhong et al. · Sequential Analysis · 2022
Group testing (pooling) is a commonly used method while screening for rare diseases, especially for large-scale screening. In recent years there has been growing interest in direct analysis of quantitative measures to take advantage of full information. In this study, we develop a pooling procedure for identification of infected specimens and the measurement is quantitative. Exclusive simulations are conducted to investigate the performance of our procedure, “Qpool,” under a variety of scenarios. We also demonstrate its application in routine monitoring of Listeria monocytogenes.
Cited by 0
Ole Jensen, Erik Paaske · 2002
We describe a concatenated coding system with iterated sequential inner decoding. The system uses convolutional codes of very long constraint length and operates on iterations between an inner Fano decoder and an outer Reed-Solomon decoder.
Cited by 0
Rajesh Sundaresan, Sergio Verdú · IEEE Transactions on Information Theory · 2000
We show the existence of a good tree code with a sequential decoder for the exponential server timing channel. The expected number of computations before moving one step ahead is upper-bounded by a finite number. The rate of information transfer for this code is /spl mu//(2e) nats per second i.e., one half of the capacity. The cutoff rate for the exponential server queue is therefore at least /spl mu//(2u) nats per second.
Cited by 32
Haggai Kfir, Ido Kanter · Physica A Statistical Mechanics and its Applications · 2003
Cited by 97Open access
Anisha Banerjee, Andreas Lenz, Antonia Wachter-Zeh · arXiv (Cornell University) · 2022
Sequential decoding, commonly applied to substitution channels, is a sub-optimal alternative to Viterbi decoding with significantly reduced memory costs. In this work, a sequential decoder for convolutional codes over channels that are prone to insertion, deletion, and substitution errors, is described and analyzed. Our decoder expands the code trellis by a new channel-state variable, called drift state, as proposed by Davey and MacKay. A suitable decoding metric on that trellis for sequential decoding is derived, generalizing the original Fano metric. The decoder is also extended to facilitate the simultaneous decoding of multiple received sequences that arise from a single transmitted sequence. Under low-noise environments, our decoding approach reduces the decoding complexity by a couple orders of magnitude in comparison to Viterbi's algorithm, albeit at slightly higher bit error rates. An analytical method to determine the computational cutoff rate is also suggested. This analysis is supported with numerical evaluations of bit error rates and computational complexity, which are compared with respect to optimal Viterbi decoding.
Cited by 0Open access