Vo TAM VAN Hajime MATSUI Seiichi MITA
Generalized quasi-cyclic (GQC) codes form a wide and useful class of linear codes that includes thoroughly quasi-cyclic codes, finite geometry (FG) low density parity check (LDPC) codes, and Hermitian codes. Although it is known that the systematic encoding of GQC codes is equivalent to the division algorithm in the theory of Grobner basis of modules, there has been no algorithm that computes Grobner basis for all types of GQC codes. In this paper, we propose two algorithms to compute Grobner basis for GQC codes from their parity check matrices; we call them echelon canonical form algorithm and transpose algorithm. Both algorithms require sufficiently small number of finite-field operations with the order of the third power of code-length. Each algorithm has its own characteristic. The first algorithm is composed of elementary methods and is appropriate for low-rate codes. The second algorithm is based on a novel formula and has smaller computational complexity than the first one for high-rate codes with the number of orbits (cyclic parts) less than half of the code length. Moreover, we show that a serial-in serial-out encoder architecture for FG LDPC codes is composed of linear feedback shift registers with the size of the linear order of code-length; to encode a binary codeword of length n, it takes less than 2n adder and 2n memory elements.
In this letter, we propose a two-bit representation method for turbo decoder extrinsic information based on bit error count minimization and parameter reset. We show that the performance of the proposed system approaches that of the full precision decoder within 0.17 dB and 0.48 dB at 1 % packet error rate for packet lengths of 500 and 10,000 information bits. The idea of parameter reset we introduce can be used not only in turbo decoder but also in many other iterative algorithms.
A direct short proof of Horiguchi's formula for error values in alternant codes is provided. Horiguchi's formula employs only output polynomials of Berlekamp-Massey algorithm, which has less computational complexity than extended Euclidean algorithm for decoding alternant codes. As an application of our proof, we provide an explicit formula for the generator and parity check matrices of alternant codes and their singly- and doubly-extended codes.
Masato TAJIMA Koji OKINO Takashi MIYAGOSHI
In this paper, we extend the conventional error-trellis construction for convolutional codes to the case where a given check matrix H(D) has a factor Dl in some column (row). In the first case, there is a possibility that the size of the state space can be reduced using shifted error-subsequences, whereas in the second case, the size of the state space can be reduced using shifted syndrome-subsequences. The construction presented in this paper is based on the adjoint-obvious realization of the corresponding syndrome former HT(D). In the case where all the columns and rows of H(D) are delay free, the proposed construction is reduced to the conventional one of Schalkwijk et al. We also show that the proposed construction can equally realize the state-space reduction shown by Ariel et al. Moreover, we clarify the difference between their construction and that of ours using examples.
A switching type-II hybrid ARQ scheme with rate compatible punctured turbo (RCPT) codes is proposed in this letter. The proposed scheme combines three retransmission schemes by minimizing a cost function that yields a compromise between throughput and delay time. The performance of the proposed algorithm is evaluated by computer simulations. Compared with conventional hybrid ARQ algorithms, the proposed algorithm can offer almost the same throughput performance with smaller time delay.
Masanori HIROTOMO Masami MOHRI Masakatu MORII
Low-density parity-check (LDPC) codes are linear block codes defined by sparse parity-check matrices. The codes exhibit excellent performance under iterative decoding, and the weight distribution is used to analyze lower error probability of their decoding performance. In this paper, we propose a probabilistic method for computing the weight distribution of LDPC codes. The proposed method efficiently finds low-weight codewords in a given LDPC code by using Stern's algorithm, and stochastically computes the low part of the weight distribution from the frequency of the found codewords. It is based on a relation between the number of codewords with a given weight and the rate of generating the codewords in Stern's algorithm. In the numerical results for LDPC codes of length 504, 1008 and 4896, we could compute the weight distribution by the proposed method with greater accuracy than by conventional methods.
Min-Ho JANG Beomkyu SHIN Woo-Myoung PARK Jong-Seon NO Dong-Joon SHIN
In this letter, we analyze the convergence speed of layered decoding of block-type low-density parity-check codes and verify that the layered decoding gives faster convergence speed than the sequential decoding with randomly selected check node subsets. Also, it is shown that using more subsets than the maximum variable node degree does not improve the convergence speed.
Tarkesh PANDE Heon HUH James KROGMEIER David LOVE
Continuous phase modulation (CPM) is a non-linear modulation technique whose power and bandwidth efficiency make it an attractive choice for mobile communication systems. Current research has focused on devising encoding rules for using CPM over multiple-input multiple-output (MIMO) systems in order to obtain the improved bit error rate (BER) and high data rates promised by MIMO technology. In this paper, optimal and suboptimal non-coherent receivers for a class of CPM signals called orthogonal space-time CPM (OST-CPM) are derived under a quasi-static fading channel assumption. The performance of these receivers is characterized and shown to achieve the same diversity order as that of the corresponding optimal coherent receiver.
Naoya ONIZAWA Takahiro HANYU Vincent C. GAUDET
This paper presents a high-throughput bit-serial low-density parity-check (LDPC) decoder that uses an asynchronous interleaver. Since consecutive log-likelihood message values on the interleaver are similar, node computations are continuously performed by using the most recently arrived messages without significantly affecting bit-error rate (BER) performance. In the asynchronous interleaver, each message's arrival rate is based on the delay due to the wire length, so that the decoding throughput is not restricted by the worst-case latency, which results in a higher average rate of computation. Moreover, the use of a multiple-valued data representation makes it possible to multiplex control signals and data from mutual nodes, thus minimizing the number of handshaking steps in the asynchronous interleaver and eliminating the clock signal entirely. As a result, the decoding throughput becomes 1.3 times faster than that of a bit-serial synchronous decoder under a 90 nm CMOS technology, at a comparable BER.
In digital communication systems employing binary phase-shift keying and non-data-aided carrier phase recovery, a 180 carrier phase ambiguity is inevitable. Here, we propose a simple modification to the standard regular repeat-accumulate (RA) code structure by exploiting the differential encoding inherent to the inner encoder of RA codes resulting in codes that are 180 rotationally invariant. The proposed code structure exhibit performance virtually identical to that of standard regular RA codes with zero carrier phase offset under both zero and 180 carrier phase offsets with negligible additional hardware complexity.
Harumichi NISHIMURA Rudy RAYMOND
Quantum random access coding (QRAC) is one of the basic tools in quantum computing. It uses a quantum state for encoding the sender's bit string so that the receiver can recover any single bit of the bit string with high probability. This article surveys recent developments of QRAC, with some concrete examples of QRAC using one quantum bit, and its applications, focusing on communication complexity and locally decodable codes.
Yoshihide TONOMURA Daisuke SHIRAI Takayuki NAKACHI Tatsuya FUJII Hitoshi KIYA
In this paper, we introduce layered low-density generator matrix (Layered-LDGM) codes for super high definition (SHD) scalable video systems. The layered-LDGM codes maintain the correspondence relationship of each layer from the encoder side to the decoder side. This resulting structure supports partial decoding. Furthermore, the proposed layered-LDGM codes create highly efficient forward error correcting (FEC) data by considering the relationship between each scalable component. Therefore, the proposed layered-LDGM codes raise the probability of restoring the important components. Simulations show that the proposed layered-LDGM codes offer better error resiliency than the existing method which creates FEC data for each scalable component independently. The proposed layered-LDGM codes support partial decoding and raise the probability of restoring the base component. These characteristics are very suitable for scalable video coding systems.
Chang-Rae JEONG Hyo-Yol PARK Kwang-Soon KIM Keum-Chan WHANG
In this paper, an efficient partial incremental redundancy (P-IR) scheme is proposed for an H-ARQ using block type low density parity check (B-LDPC) codes. The performance of the proposed P-IR scheme is evaluated in an HSDPA system using IEEE 802.16e B-LDPC codes. Simulation results show that the proposed H-ARQ using IEEE 802.16e B-LDPC codes outperforms the H-ARQ using 3GPP turbo codes.
This paper is concerned with timing synchronization of high rates UWB signals operating in a dense multipath environment, where access must tackle inter-frame interference (IFI), inter-symbol interference (ISI) and even multi-user interference (MUI). A training-based joint timing and channel estimation scheme is proposed, which is resilient to IFI, ISI, MUI and pulse distortion. A low-complexity detection scheme similar to transmit-reference (TR) scheme comes out as a by-product. For saving the training symbols, we further develop an extended decision-directed (DD) scheme. A lower bound on the probability of correct detection is derived which agrees well with the simulated result for moderate to high SNR values. The results show that the proposed algorithm achieves a significant performance gain in terms of mean square error and bit error rate in comparison to the "timing with dirty templates" (TDT) algorithms.
Hideki YAGI Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
Code construction for digital fingerprinting, which is a copyright protection technique for multimedia, is considered. Digital fingerprinting should deter collusion attacks, where several fingerprinted copies of the same content are mixed to disturb their fingerprints. In this paper, we consider the averaging attack, which is known to be effective for multimedia fingerprinting with the spread spectrum technique. We propose new methods for constructing fingerprinting codes to increase the coding rate of conventional fingerprinting codes, while they guarantee to identify the same number of colluders. Due to the new fingerprinting codes, the system can deal with a larger number of users to supply digital contents.
This letter presents a necessary and sufficient condition for a class of quasi-cyclic low-density parity-check (QC LDPC) codes without girth four. Girth-four property of a class of QC LDPC codes is investigated. Good QC LDPC codes without girth four can be constructed by selecting proper shifting factors according to the proposed theorems. Examples are provided to verify the theorems. The simulation results show that the QC LDPC codes without girth four achieve a better BER performance compared with that of randomly constructed LDPC codes.
Yong-Chun PIAO Jinwoo CHOE Wonjin SUNG Dong-Joon SHIN
In this letter, we propose combinatorial and search construction methods of 2-D multi-weight optical orthogonal codes (OOCs) with autocorrelation 0 and crosscorrelation 1, called multi-weight single or no pulse per row (MSNPR) codes. An upper bound on the size of MSNPR codes is derived and the performance of MSNPR codes is compared to those of other OOCs in terms of the bit error rate (BER) and evaluated using blocking probability. It is also demonstrated that the MSNPR codes can be flexibly constructed for different applications, providing the scalability to optical CDMA networks.
Manabu KOBAYASHI Hideki YAGI Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
In this paper, we analyze the robustness for low-density parity-check (LDPC) codes over the Gilbert-Elliott (GE) channel. For this purpose we propose a density evolution method for the case where LDPC decoder uses the mismatched parameters for the GE channel. Using this method, we derive the region of tuples of true parameters and mismatched decoding parameters for the GE channel, where the decoding error probability approaches asymptotically to zero.
Cheon Ho LEE Young Chai KO Jun HEO
This paper presents an improved min-sum iterative decoding scheme for regular and irregular LDPC codes. The proposed decoding scheme scales the extrinsic soft information from variable nodes to check. Different scaling factors are applied for iterations and the scaling factors are obtained by a simplified vector optimization method.
Haruo OGIWARA Kyouhei SHIMAMURA Toshiyuki SHOHON
This paper proposes methods to improve soft-input and soft-output decoding performance of BCH codes by sum-product algorithm (SPA). A method to remove cycles of length four (RmFC) in the Tanner graph has been proposed. However, the RmFC can not realize good decoding performance for BCH codes which have more than one error correcting capability. To overcome this problem, this paper proposes two methods. One is to use a parity check matrix of the echelon canonical form as the starting check matrix of RmFC. The other is to use a parity check matrix that is concatenation (ConC) of multiple parity check matrices. For BCH(31,11,11) code, SPA with ConC realizes Eb/No 3.7 dB better at bit error rate 10-5 than the original SPA, and 3.1 dB better than the SPA with only RmFC.