2013/01/15 by Qin Huang, Li Tang, Huang, Qin +7
Computer Science · Engineering · Mathematics · #Advanced Wireless Communication Techniques #Coding theory and cryptography #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1301.3220
8 pages, 2 figures
arxiv created 2013/01/15 · openalex publication_date 2013/01/15 · arxiv updated 2013/01/16 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
The encoding complexity of a general (en,ek) quasi-cyclic code is O[(e2)(n-k)k]. This paper presents a novel low-complexity encoding algorithm for quasi-cyclic (QC) codes based on matrix transformation. First, a message vector is encoded into a transformed codeword in the transform domain. Then, the transmitted codeword is obtained from the transformed codeword by the inverse Galois Fourier transform. For binary QC codes, a simple and fast mapping is required to post-process the transformed codeword such that the transmitted codeword is binary as well. The complexity of our proposed encoding algorithm is O[e(n-k)k] symbol operations for non-binary codes and O[ek(n-k)(log2 e)] bit operations for binary codes. These complexities are much lower than their traditional counterpart O[(e2)(n-k)k]. For example, our complexity of encoding a 64-ary (4095,2160) QC code is only 1.59% of that of traditional encoding, and our complexities of encoding the binary (4095, 2160) and (8176, 7154) QC codes are respectively 9.52% and 1.77% of those of traditional encoding. We also study the application of our low-complexity encoding algorithm to one of the most important subclasses of QC codes, namely QC-LDPC codes, especially when their parity-check matrices are rank deficient.