Babak Mahmoudi (354650), Justin C. Sanchez (137025) · Figshare · 2015
1<p>Speed is defined by the number of trials to converge to a control policy to solve the task consistently.</p>2<p>Accuracy is defined by the rate of success after convergence. For the first 100 trials of “Target 4” acquisition and “All 4 Targets” tasks that the decoder did not converge, the accuracy is computed during adaptation.</p>
Cited by 0Open access
Irwin Lebow · 1963
Abstract : This report contains a qualitative discussion of sequential decoding directed toward the non-specialist in information theory. Both the Wozencraft and Fano algorithms are included. The description of sequential decoding is pre ceded by a summary of the general problem of probabilistic coding and decoding.
Cited by 1
Kamil Sh. Zigangirov · 1994
Cited by 0
Min-Ho Lee (1567513), John Williamson (246543), Young-Jin Kee (8190312) et al. · Figshare · 2019
<p>The decoding accuracy for individual subjects and their average. The performance (y-axis) was calculated from one to a maximum of ten sequences (x-axis).</p>
Cited by 0Open access
John E. Savage · DSpace@MIT (Massachusetts Institute of Technology) · 1965
Bibliography: p. 76-77.
Cited by 17Open access
Johan Nyström, Rolf Johannesson, Kamil Sh. Zigangirov · Lund University Publications (Lund University) · 1993
Cited by 6
2008
Abstract-The use of sequential decoding in multiple access channels is considered. The Fano metric, which achieves all achievable rates in the one-user case, fails to do so in the multiuser case. A new metric is introduced and an inner bound is given to its achievable rate region. This inner bound region is large enough to encourage the use of sequential decoding in practice. The new metric is optimal, in the sense of achieving all achievable rates, in the case = of one-user and painvise-reversible chan-nels. Whether the metic is optimal for all multiple access channels remains an open problem. It is worth noting that even in the one-user case, the new metric differs from the Fano metric in a nontrivial way, showing that the Fano metric is not uniquely optimal for such channels. A new and stricter criterion of achievability in sequential decoding is also introduced and examined. W
Cited by 0
Seth Lloyd, Vittorio Giovannetti, Lorenzo Maccone · Physical Review Letters · 2011
We study the transmission of classical information in quantum channels. We present a decoding procedure that is very simple but still achieves the channel capacity. It is used to give an alternative straightforward proof that the classical capacity is given by the regularized Holevo bound. This procedure uses only projective measurements and is based on successive "yes-no" tests only.
Cited by 41Open access
Mohammad Rowshan, Andreas Burg, Emanuele Viterbo · 2021
In the Shannon lecture at the 2019 International Symposium on Information Theory (ISIT), Arıkan proposed to employ a one-to-one convolutional transform as a pre-coding step before the polar transform. The resulting codes of this concatenation are called polarization-adjusted convolutional (PAC) codes. In this scheme, a pair of polar mapper and demapper as pre- and postprocessing devices are deployed around a memoryless channel, which provides polarized information to an outer decoder leading to improved error correction performance of the outer code. In this paper, the list decoding and sequential decoding (including Fano decoding and stack decoding) are first adapted for use to decode PAC codes. Then, to reduce the complexity of sequential decoding of PAC/polar codes, we propose (i) an adaptive heuristic metric, (ii) tree search constraints for backtracking to avoid exploration of unlikely sub-paths, and (iii) tree search strategies consistent with the pattern of error occurrence in polar codes. These contribute to the reduction of the average decoding time complexity from 50% to 80%, trading with 0.05 to 0.3 dB degradation in error correction performance within FER=10^-3 range, respectively, relative to not applying the corresponding search strategies. Additionally, as an important ingredient in Fano decoding of PAC/polar codes, an efficient computation method for the intermediate LLRs and partial sums is provided. This method is effective in backtracking and avoids storing the intermediate information or restarting the decoding process. Eventually, all three decoding algorithms are compared in terms of performance, complexity, and resource requirements.
Cited by 3Open access
Charles W. Niessen · DSpace@MIT (Massachusetts Institute of Technology) · 1965
Bibliography: p.76.
Cited by 2Open access
P. Chevillat, Daniel J. Costello · IEEE Transactions on Communications · 1976
The relationship between the column distance function and the computational effort of sequential decoding is studied and the results of computer simulations are reported. A table of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R = 1/2</tex> codes having good free distance and optimum average column distance function (CDF) is presented.
Cited by 25
Ravi Sivasanlraran, Stephen McLaughlin, Laura L. McPhctcrs · 1999
Summary: Turbc4ke codes have been propmd for improving the performance of PR-equalized magnetic recording channeh [l], and it j, now well-known that thee provide 3 - 6 dE3 of coding gain. The primary impediment to their implementation is the complexity of the dewdcr. In thili paper, we wnsider the use of a sequential deader that can dramatically reduce the wmputational burden. Simulations for a ratc 4/5 turbo code on a precoded PR4-Equalized chanuel with AWGN Jhows a gain of about 3.5 dB at BERs 5 lo-' for a block length of N = 1024 bits, over the uncoded channel. Further increase of around 0.5 dB is seen with N = 4096 bitsfilock. Sequential 'stack' decoding of convolutional codes is a well known mcthod for reducing the computational complexity over maximum likelihood Vitcrbi decoding. In [2], it is shown how the stack decoder can be mded to produce Jolt outputs Cor raursive convolutional codes, and then subsequently be used to decode turbo codcu. We show here that this decoder can also he used for PR-equalized magnetic recording channels. The scqucntial decoder is a Twin-Staek decoder. whim h* the capability of retaining information about ell thc transitions into any state at any imtant of time. The decoder is capable of acting as a soft-out dewder, and the post processing unit that gcncrates the log likelihood ratio on the input sequence approaches the maximum a-postffwri decoder iC the pmbahility of the unexpanded paths in the stack are negligible. For complete details on the Twin Stad? decoder see [2j. The system under wmideration is yhown in Figurc 1. Results: Figure 2 shows the pcrformance of the soft-out Twin Stack dewdcr in the combined turh*dxoding and equalization system under consideration [l]. We find that the proposed decoder shows a gain of around 4.0 dB over the nncoded channel at BE& 5 W5 for a block lcngth of N = 4096 bits. Although the decodcr fall short of the performance of a classical BCJR-based turbo decoder by about 1.5 dB for the same configuration, we find that the complexity of the propmed decoder decreases aaymptotidy with SNRs and iterations, and is roughly qual to I/(number of states in the encoder). Thus providing a good trade-off hetwea performance and complexity. Fwe 3 shows the average computational complexity of both BCJR and Twin Stack decodm. The latency parameter is defined as the product of the average decoding time per packct and the number of computations performed per decoded bit. The BCJR decoder has a fixed latency independent of the SNR and the iteration, and is equal to the numbcr of states in the encoder, (16 in our Fiure). On the other hand, the Twii Stada decoder shows a latency which is a function of the SNR and the number of iterations. In Fiure 3, we have shown the Latexicy for two values of SNR =
Cited by 0
Barry Harold. Lerich · Calhoun: The Naval Postgraduate School Institutional Archive (Naval Postgraduate School) · 1971
A discussion of convolutional encoding and sequential decoding is given as background for the experimental phase of this research. A modified stack algorithm is programmed to simulate a sequential decoder for use in the study of time-varying convolutional codes. The decoder simulator is used to analyze the structure of codes with the aim of finding a systematic method by which to construct time-varying convolutional codes with good decoding properties. Some difficulties in construction techniques are discussed. Extensive computer simulation comparing decoding performance of time-varying codes to that of fixed codes Is reported. The conclusion of these comparisons is that the time-varying codes studied thus far are of theoretical interest only.
Cited by 0
Defense Technical Information Center (DTIC) · 1961
This analysis summarizes the study of Sequential Decoding for the Binary Symmetric Channel. The program included a theoretical study of various decoding algorithms, and an experimental investigation employing a general-purpose digital computer. (Author)
Cited by 0
Ilya Timokhin, Fedor Ivanov · Applied Sciences · 2024
Polar codes have established themselves as a cornerstone in modern error correction coding due to their capacity-achieving properties and practical implementation advantages. However, decoding polar codes remains a computationally intensive task. In this paper, we introduce a novel approach to improve the decoding efficiency of polar codes by integrating the threshold-based SC-Creeper decoding algorithm, originally designed for convolutional codes. Our proposed decoder with an additional cost function seamlessly merges two established decoding paradigms, namely the stack and Fano approaches. The core idea is to leverage the strengths of both decoding techniques to strike a balance between computational efficiency and performance, with an additional method of controlling movement along a code tree. Simulations demonstrate the superiority of the proposed improved SC-Creeper decoder with tuned parameters. The improved SC-Creeper decoder achieves the performance of the CA-SCL-8 decoder in terms of high code rates and overcomes it in terms of the N=1024 code length, while simultaneously surpassing the efficiency of the traditional Fano decoding algorithm.
Cited by 4Open access
Andreas Knaut, Martin Paschmann · Econstor (Econstor) · 2017
Restricted participation in sequential markets may cause high price volatility and welfare losses. In this paper we therefore analyze the drivers of restricted participation in the German intraday auctin which is a short-term electricity market with quarter-hourly products. Applying a fundamental electricity market model with 15-minute temporal resolution, we identify the lack of sub-hourly market coupling being the most relevant driver and restricted participation. We derive a proxy for price volatility and find that full market coupling may trigger quarter-hourly price valatility to decrease by a factor close to four.
Cited by 0Open access
Vladimir Sidorenko, Rolf Johannesson, Kamil Sh. Zigangirov · IEEE Transactions on Information Theory · 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 0
Fu-Quan Wang, Daniel J. Costello · IEEE Transactions on Information Theory · 1994
An erasure-free sequential decoding algorithm for trellis codes, called the buffer looking algorithm (BLA), is introduced. Several versions of the algorithm can be obtained by choosing certain parameters and selecting a resynchronization scheme. These can be categorized as block decoding or continuous decoding, depending on the resynchronization scheme. Block decoding is guaranteed to resynchronize at the beginning of each block, but suffers some rate loss when the block length is relatively short. The performance of a typical block decoding scheme is analyzed, and we show that significant coding gains over Viterbi decoding can be achieved with much less computational effort. A resynchronization scheme is proposed for continuous sequential decoding. It is shown by analysis and simulation that continuous sequential decoding using this scheme has a high probability of resynchronizing successfully. This new resynchronization scheme solves the rate loss problem resulting from block decoding. The channel cutoff rate, demodulator quantization, and the tail's influence on performance are also discussed. Although this paper considers only the decoding of trellis codes, the algorithm can also be applied to the decoding of convolutional codes.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 13
Mohsen Moradi, Salman Habib, Vahid Nourozi et al. · ArXiv.org · 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
Doğrusöz, Bekir Ahmet · Bilkent University Institutional Repository (Bilkent University) · 2016
Ankara : Department of Electrical and Electronics Engineering and Institute of Engineering and Science, Bilkent Univ., 1997.
Cited by 0Open access