Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEnumeration of Minimum Hamming Weight Polar Codewords with Sublinear Complexity
53
0
0.0
(
0
)
Added by
Jincheng Dai
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Polar code, with explicit construction and recursive structure, is the latest breakthrough in channel coding field for its low-complexity and theoretically capacity-achieving property. Since polar codes can approach the maximum likelihood performance under successive cancellation list decoding (SCLD), its decoding performance can be evaluated by Bonferroni-type bounds (e.g., union bound) in which the Hamming weight spectrum will be used. Especially, the polar codewords with minimum Hamming weight (PC-MHW) are the most important item in that bound because they make major contributions to the decoding error pattern particularly at high signal-to-noise-ratio. In this work, we propose an efficient strategy for enumerating the PC-MHW and its number. By reviewing the inherent reason that PC-MHW can be generated by SCLD, we obtain some common features of PC-MHW captured by SCLD. Using these features, we introduce a concept of zero-capacity bit-channel to obtain a tight upper bound for the number of PC-MHW, whose computing complexity is sublinear with code length. Furthermore, we prove that the proposed upper bound is really the exact number of PC-MHW in most cases. Guided by the bound and its theoretical analysis, we devise an efficient SCLD-based method to enumerate PC-MHW, which requires less than half of the list size compared with the existing methods.
rate research
Read More
In this paper, the minimum weight distributions (MWDs) of polar codes and concatenated polar codes are exactly enumerated according to the distance property of codewords. We first propose a sphere constraint based enumeration method (SCEM) to analyze the MWD of polar codes with moderate complexity. The SCEM exploits the distance property that all the codewords with the identical Hamming weight are distributed on a spherical shell. Then, based on the SCEM and the Plotkins construction of polar codes, a sphere constraint based recursive enumeration method (SCREM) is proposed to recursively calculate the MWD with a lower complexity. Finally, we propose a parity-check SCEM (PC-SCEM) to analyze the MWD of concatenated polar codes by introducing the parity-check equations of outer codes. Moreover, due to the distance property of codewords, the proposed three methods can exactly enumerate all the codewords belonging to the MWD. The enumeration results show that the SCREM can enumerate the MWD of polar codes with code length up to $2^{14}$ and the PC-SCEM can be used to optimize CRC-polar concatenated codes.
This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is $O(N^{1-1/mu})$, where $N$ is the block length and $mu$ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate $0$ or $1$.
Projective Reed-Muller codes correspond to subcodes of the Reed-Muller code in which the polynomials being evaluated to yield codewords, are restricted to be homogeneous. The Generalized Hamming Weights (GHW) of a code ${cal C}$, identify for each dimension $ u$, the smallest size of the support of a subcode of ${cal C}$ of dimension $ u$. The GHW of a code are of interest in assessing the vulnerability of a code in a wiretap channel setting. It is also of use in bounding the state complexity of the trellis representation of the code. In prior work by the same authors, a code-shortening algorithm was employed to derive upper bounds on the GHW of binary projective, Reed-Muller (PRM) codes. In the present paper, we derive a matching lower bound by adapting the proof techniques used originally for Reed-Muller (RM) codes by Wei. This results in a characterization of the GHW hierarchy of binary PRM codes.
We study affine cartesian codes, which are a Reed-Muller type of evaluation codes, where polynomials are evaluated at the cartesian product of n subsets of a finite field F_q. These codes appeared recently in a work by H. Lopez, C. Renteria-Marquez and R. Villareal and, in a generalized form, in a work by O. Geil and C. Thomsen. Using methods from Grobner basis theory we determine the second Hamming weight (also called next-to-minimal weight) for particular cases of affine cartesian codes and also some higher Hamming weights of this type of code.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
