Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstruction of Polar Codes with Reinforcement Learning
116
0
0.0
(
0
)
Added by
Yun Liao
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper formulates the polar-code construction problem for the successive-cancellation list (SCL) decoder as a maze-traversing game, which can be solved by reinforcement learning techniques. The proposed method provides a novel technique for polar-code construction that no longer depends on sorting and selecting bit-channels by reliability. Instead, this technique decides whether the input bits should be frozen in a purely sequential manner. The equivalence of optimizing the polar-code construction for the SCL decoder under this technique and maximizing the expected reward of traversing a maze is drawn. Simulation results show that the standard polar-code constructions that are designed for the successive-cancellation decoder are no longer optimal for the SCL decoder with respect to the frame error rate. In contrast, the simulations show that, with a reasonable amount of training, the game-based construction method finds code constructions that have lower frame-error rate for various code lengths and decoders compared to standard constructions.
rate research
Read More
In this paper we address the problem of selecting factor-graph permutations of polar codes under belief propagation (BP) decoding to significantly improve the error-correction performance of the code. In particular, we formalize the factor-graph permutation selection as the multi-armed bandit problem in reinforcement learning and propose a decoder that acts like an online-learning agent that learns to select the good factor-graph permutations during the course of decoding. We use state-of-the-art algorithms for the multi-armed bandit problem and show that for a 5G polar codes of length 128 with 64 information bits, the proposed decoder has an error-correction performance gain of around 0.125 dB at the target frame error rate of 10^{-4}, when compared to the approach that randomly selects the factor-graph permutations.
Polar codes are the first class of constructive channel codes achieving the symmetric capacity of the binary-input discrete memoryless channels. But the corresponding code length is limited to the power of two. In this paper, we establish a systematic framework to design the rate-compatible punctured polar (RCPP) codes with arbitrary code length. A new theoretic tool, called polar spectra, is proposed to count the number of paths on the code tree with the same number of zeros or ones respectively. Furthermore, a spectrum distance SD0 (SD1) and a joint spectrum distance (JSD) are presented as performance criteria to optimize the puncturing tables. For the capacity-zero puncturing mode (punctured bits are unknown to the decoder), we propose a quasi-uniform puncturing algorithm, analyze the number of equivalent puncturings and prove that this scheme can maximize SD1 and JSD. Similarly, for the capacity-one mode (punctured bits are known to the decoder), we also devise a reversal quasi-uniform puncturing scheme and prove that it has the maximum SD0 and JSD. Both schemes have a universal puncturing table without any exhausted search. These optimal RCPP codes outperform the performance of turbo codes in LTE wireless communication systems.
We consider an agent interacting with an unmodeled environment. At each time, the agent makes an observation, takes an action, and incurs a cost. Its actions can influence future observations and costs. The goal is to minimize the long-term average cost. We propose a novel algorithm, known as the active LZ algorithm, for optimal control based on ideas from the Lempel-Ziv scheme for universal data compression and prediction. We establish that, under the active LZ algorithm, if there exists an integer $K$ such that the future is conditionally independent of the past given a window of $K$ consecutive actions and observations, then the average cost converges to the optimum. Experimental results involving the game of Rock-Paper-Scissors illustrate merits of the algorithm.
Recently, it was discovered by several authors that a $q$-ary optimal locally recoverable code, i.e., a locally recoverable code archiving the Singleton-type bound, can have length much bigger than $q+1$. This is quite different from the classical $q$-ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special case). This discovery inspired some recent studies on length of an optimal locally recoverable code. It was shown in cite{LXY} that a $q$-ary optimal locally recoverable code is unbounded for $d=3,4$. Soon after, it was proved that a $q$-ary optimal locally recoverable code with distance $d$ and locality $r$ can have length $Omega_{d,r}(q^{1 + 1/lfloor(d-3)/2rfloor})$. Recently, an explicit construction of $q$-ary optimal locally recoverable codes for distance $d=5,6$ was given in cite{J18} and cite{BCGLP}. In this paper, we further investigate construction optimal locally recoverable codes along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and cite{J18}, we equip parity-check matrices with the Vandermond structure. It is turns out that a parity-check matrix with the Vandermond structure produces an optimal locally recoverable code must obey certain disjoint property for subsets of $mathbb{F}_q$. To our surprise, this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in cite{GXY} for $dgeq 7$. In addition, for $d=6$, we are able to remove the constraint required in cite{J18} that $q$ is even.
Polar codes with memory (PCM) are proposed in this paper: a pair of consecutive code blocks containing a controlled number of mutual information bits. The shared mutual information bits of the succeeded block can help the failed block to recover. The underlying polar codes can employ any decoding scheme such as the successive cancellation (SC) decoding (PCM-SC), the belief propagation (BP) decoding (PCM-BP), and the successive cancellation list (SCL) decoding (PCM-SCL). The analysis shows that the packet error rate (PER) of PCM decreases to the order of PER squared while maintaining the same complexity as the underlying polar codes. Simulation results indicate that for PCM-SC, the PER is comparable to (less than 0.3 dB) the stand-alone SCL decoding with two lists for the block length $N=256$. The PER of PCM-SCL with $L$ lists can match that of the stand-alone SCL decoding with $2L$ lists. Two hardware decoders for PCM are also implemented: the in-serial (IS) decoder and the low-latency interleaved (LLI) decoder. For $N=256$, synthesis results show that in the worst case, the latency of the PCM LLI decoder is only $16.1%$ of the adaptive SCL decoder with $L=2$, while the throughput is improved by 13 times compared to it.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
