Improved method for searching interleavers from a certain set using Garello’s method with applications for the LTE standard

In this paper, we propose a method for searching interleavers within a certain class, with the aim of designing turbo codes with good distance spectrum. The method is based on a modified version of Garello’s algorithm and consists in the calculation of frame error rate truncated upper bound. Here, it is applied to quadratic permutation polynomial (QPP) interleavers able to outperform those chosen for the long-term evolution (LTE) standard, for lengths up to 1,504 bits. Three classes of interleavers have been analyzed: (1) the set of QPP interleavers with the largest spread, (2) the set of QPP interleavers with a spread parameter equal to that of LTE interleaver and the highest refined nonlinearity degree, and (3) the complete set of all QPP interleavers for lengths up to 1,008. The distance spectrum optimization is made for all classes. Compared to previous methods for finding QPP-based interleavers, the search complexity is reduced, with improved performances in terms of search time, allowing interleavers of higher length. For lengths up to approximately 450, the best interleavers were found in the first class. For longer lengths, the second class contained the best ones.     

A simple method to determine the number of true different quadratic and cubic permutation polynomial based interleavers for turbo codes

Interleavers are important blocks of the turbo codes, their types and dimensions having a significant influence on the performances of the mentioned codes. If appropriately chosen, the permutation polynomial (PP) based interleavers lead to remarkable performances of these codes. The most used interleavers from this category are quadratic permutation polynomial (QPP) and cubic permutation polynomial (CPP) based ones. In this paper, we determine the number of different QPPs and CPPs that cannot be reduced to linear permutation polynomials (LPPs) or to QPPs or LPPs, respectively. They are named true QPPs and true CPPs, respectively. Our analysis is based on the necessary and sufficient conditions for the coefficients of second and third degree polynomials to be QPPs and CPPs, respectively, and on the Chinese remainder theorem. This is of particular interest when we need to find QPP or CPP based interleavers for turbo codes.     

Interleavers for turbo codes using permutation polynomials over integer rings

A class of deterministic interleavers for turbo codes (TCs) based on permutation polynomials over /spl Zopf//sub N/ is introduced. The main characteristic of this class of interleavers is that they can be algebraically designed to fit a given component code. Moreover, since the interleaver can be generated by a few simple computations, storage of the interleaver tables can be avoided. By using the permutation polynomial-based interleavers, the design of the interleavers reduces to the selection of the coefficients of the polynomials. It is observed that the performance of the TCs using these permutation polynomial-based interleavers is usually dominated by a subset of input weight 2m error events. The minimum distance and its multiplicity (or the first few spectrum lines) of this subset are used as design criterion to select good permutation polynomials. A simple method to enumerate these error events for small m is presented. Searches for good interleavers are performed. The decoding performance of these interleavers is close to S-random interleavers for long frame sizes. For short frame sizes, the new interleavers outperform S-random interleavers.     

About minimum distance for QPP interleavers

Two search methods of quadratic permutation polynomials (QPP) for interleavers used in turbo codes are proposed. These methods lead to larger minimum distances and smaller multiplicities compared to the interleavers proposed by Takeshita in (Takeshita 1). The search is accomplished in a limited set of polynomials, that is, those for which the spreading factor and Ω′ metric are maximum. The minimum distance is computed by means of Garello algorithm in which the maximum weight of information sequence is 3 or 4, reducing the search time. The results obtained for two particular component codes show the efficiency of the proposed methods.     

Optimized prunable single-cycle interleavers for turbo codes

This paper is aimed at the problem of designing optimized interleavers for parallel concatenated convolutional codes (PCCC) that satisfy several requirements simultaneously: 1) designing interleavers tailored to the constituent codes of the PCCC; 2) improving the distance spectra of the resulting turbo codes which dominate their asymptotic performance; 3) constructing optimized interleavers recursively so that they are implicitly prunable; and 4) completely avoiding short permutation cycles in order to reduce the risk of having strong correlations between the extrinsic information during iterative decoding. To this end, we present two theorems that lead to a modification of a previously developed iterative interleaver growth algorithm (IGA) that can be used to design optimized variable-length interleavers, whereby at every length the optimized permutation implemented by the interleaver is a single-cycle permutation. Two more modifications of the IGA are presented to improve the performance of the optimized interleavers at a reduced complexity. The optimization is achieved via constrained minimization of a cost function closely related to the asymptotic bit-error rate or frame-error rate of the code.     

Performance of Möbius Interleavers for Turbo Codes

In this paper, we study the minimum free distance and error performance of turbo encoders with Möbius interleavers. In order to be capable of estimating the minimum free distance of these interleavers using binary-fixed point (BFP) algorithm, new deterministic interleavers called “truncated Möbius interleavers” are defined and constructed. It is shown how the shifted cycles of these interleavers can be related to the cycle structure of the primary Möbius transformation and its coefficients. By adjusting some parameters, an upper bound on the number of total tested BFPs for the proposed truncated Möbius interleavers is found. One distinctive property of Möbius interleavers is that their inverse can also be represented and computed with Möbius functions. Simulations are conducted to compare the error performance of the proposed truncated Möbius interleavers with quadratic permutation polynomial (QPP) interleavers whose inverses are also representable by a quadratic equation (Ryu and Takeshita in IEEE Trans Inf Theory 52(3):1254–1260, 2006). It is finally shown that the truncated Möbius interleavers can interleave sequences of information bits faster than QPP interleavers.     

Performance of HSR and QPP-based interleavers for turbo coding on power line communication systems

In this paper, the performance of different type and length interleavers for turbo codes is analyzed in the context of power line communication systems. This system typically operates in very noisy environments; the noise, in this channel, is a combination of colored, narrow band and impulsive noises; it has also strong amplitude attenuations. The digital modulation frequently employed in power line communication to counteract the channel’s noise effects is the orthogonal frequency division multiplexing due to its high spectral efficiency and robustness in multipath fading environments; hence, it is also considered in our experimentation. We report the performance of turbo codes with the two types of interleavers: the high-spread random and the based quadratic permutation polynomial. The constituent codes are part of the 3GPP standard. Finally, it is used a punctured matrix in order to achieve a coding rate of 1/2. The performance is evaluated in terms of bit error rate, through the way of simulations.     

基于余数系统与置换多项式的高速长周期伪随机序列生成方法

低复杂度长周期数字伪随机序列在现代加密、通信等系统中具有广泛的应用。该文提出一种基于余数系统和有限域置换多项式的伪随机序列生成方法。该方法基于中国剩余定理将多个互质的小周期有限域随机序列进行单射扩展生成长周期数字伪随机序列,置换多项式的迭代计算在多个并行的小动态范围有限域上进行,从而降低了硬件实现中迭代环路的计算位宽,提高了生成速率。该文还给出构建长周期伪随机序列的置换多项式参数选择方法和中国剩余定理优化方法,在现有技术平台下可轻易实现2100以上的序列周期。同时,该方法具有极大的迭代多项式选择自由度,例如仅在q2(mod)3且q503的有限域上满足要求的置换多项式就有10905种。硬件实现结构简单,基于Xilinx XC7Z020芯片实现290的随机序列仅需20个18 kbit的BRAM和少量逻辑资源,无需乘法器,生成速率可达449.236 Mbps。基于NIST的测试表明序列具有良好的随机特性。     

基于整数环QPP的逆多项式

从深空通信到移动通信,基于整数环的QPP交织器在Turbo编译码系统中的运用备受重视,在以往对QPP研究中,发现有些QPP是不存在二次逆多项式的,针对这一特点,通过运用中国剩余定理和函数逆运算的方法,给出了一种确定QPP最少次数逆多项式的充要条件,并提出了计算QPP最少次数逆多项式的明确算法。     

A cost-function based technique for design of good prunable interleavers for turbo codes

This paper addresses the design of semi-random, prunable interleavers for parallel concatenated convolutional codes (PCCC). The proposed technique is iterative and is based on the growth of a smaller interleaver up to the desired length N. The optimization is achieved via a minimization using a cost-function strictly related to both the correlation properties of the extrinsic information and the concept of spread of an interleaver. Performance of the designed interleavers are given in terms of bit error rate (BER) and frame error rate (FER). Comparisons are given with respect to other prunable and ad-hoc interleaver design techniques already proposed in literature. The designed interleavers are prunable and have a behavior very similar to the interleavers designed with techniques which maximize the spread of the permutation.     

Simple method for generating mth-order permutation polynomials over integer rings

A sufficient condition for mth-order (mges1) polynomials as permutation polynomials (PPs) over integer rings is presented and proved. Possible applications of the proposed simple mth-order PP generation method include the design of interleavers for turbo codes and generation of pseudorandom numbers     

High-performance VLSI architectures for turbo decoders with QPP interleaver

This paper analyses different VLSI architectures for 3GPP LTE/LTE-advanced turbo decoders for trade-offs in terms of throughput and area requirement. Data flow graphs for standard SISO MAP (maximum a posteriori) turbo decoder, SW – SISO MAP turbo decoder, PW SISO MAP turbo decoder have been presented, thus analysing their performance. Two variants of quadratic permutation polynomial (QPP) interleaver have been proposed which tend to simplify the complexity of ‘mod’ operator implementation and provide best compromise between area, delay and power dissipation. Implementation of decoder using one variant of QPP interleaver has also been discussed. A novel approach for area optimisation has been proposed to reduce required number of interleavers for parallel window turbo decoder. Multi-port memory has also been used for parallel turbo decoder. To increase the throughput without any effective increase in area complexity, circuit-level pipelining and retiming have been used. Proposed architectures have been synthesised using Synopsys Design Compiler using 45-nm CMOS technology.     

Interleaver properties and their applications to the trelliscomplexity analysis of turbo codes

In this paper, the basic theory of interleavers is revisited in a semi-tutorial manner, and extended to encompass noncausal interleavers. The parameters that characterize the interleaver behavior (like delay, latency, and period) are clearly defined. The input-output interleaver code is introduced and its complexity studied. Connections among various interleaver parameters are explored. The classes of convolutional and block interleavers are considered, and their practical implementation discussed. The trellis complexity of turbo codes is tied to the complexity of the constituent interleaver. A procedure of complexity reduction by coordinate permutation is also presented, together with some examples of its application     

Design of flexible-length S-random interleaver for turbo codes

We introduce a method for generating a sequence of semi-random interleavers, intended to be optimally stored and employed in a turbo coding system that requires flexibility of the input block (i.e., interleaver) size N. A distinctive feature of this method is seen in the very simple rules for obtaining shorter/longer interleavers by pruning/adding positions to the interleaver currently used in the system. For each N, the obtained bit error rate (BER) is not higher than the BER for ordinary S-random interleaver of the same N. The method always converges and is suitable for obtaining interleavers of large lengths.     

Modified Collision-Free Interleavers for High Speed Turbo Decoding

Inter-window shuffle (IWS) interleavers are a class of collision-free (CF) interleavers that have been applied to parallel turbo decoding. In this paper, we present modified IWS (M-IWS) interleavers that can further increase turbo decoding throughput only at the expense of slight performance degradation. By deriving the number of M-IWS interleavers, we demonstrate that the number is much smaller than that of IWS interleavers, whereas they both have a very simple algebraic representation. Further, it is shown by analysis that under given conditions, storage requirements of M-IWS interleavers can be reduced to only 368 storage bits for variable interleaving lengths. In order to realize parallel outputs of the on-line interleaving addresses, a low-complexity architecture design of M-IWS interleavers for parallel turbo decoding is proposed, which also supports variable interleaving lengths. Therefore, the M-IWS interleavers are very suitable for the turbo decoder in next generation communication systems with the high data rate and low latency requirements.     

A Low Complexity Algorithm for Generating Turbo Code s-Random Interleavers

In this paper we present a low complexity algorithm based on the bubble search sorting method that can be used to generate Turbo code interleavers that fulfill several criteria like spreading (s-randomness), code matched criteria and even the odd–even property for Turbo Trellis Coded Modulation. Simulation results show that for \(s < \sqrt{N/2}\) the algorithm is extremely efficient for short to medium interleaver lengths.     

Interleaver design for serially concatenated convolutional codes: theory and application

This paper addresses the problem of interleaver design for serially concatenated convolutional codes (SCCCs) tailored to the constituent codes of the SCCC configuration. We present a theoretical framework for interleaver optimization based on a cost function closely tied to the asymptotic bit-error rate (BER) of the block code C/sub s/ resulting from proper termination of the constituent codes in the SCCC code. We define a canonical form of the interleaving engine denoted as the finite state permuter (FSP) and using its structural property, develop a systematic iterative technique for construction of interleavers. The core theoretical results focus on the asymptotic behavior of a class of cost functions and their martingale property, which is then used to develop an order recursive interleaver optimization algorithm. We address the issue of the complexity of the interleaver growth algorithm presented in the paper and demonstrate that it has polynomial complexity. Subsequently, we provide details about the application of the proposed technique and present a modification of the algorithm that employs error pattern feedback for improved performance at a reduced complexity. Sample experimental results are provided for an SCCC code of rate 1/3 and information block length 320 that achieves a minimum distance of d/sub min/=44.     

Distance upper bounds and true minimum distance results for turbo-codes designed with DRP interleavers

This paper presents a number of distance upper bounds for Turbo-codes designed with dithered relative prime (drp) interleavers. These bounds help determine how much dither should be applied and which input data patterns to test when designing high-distance interleavers with different lengths. Using a block length of only 640 data bits, true minimum distances of 30, 42 and 53 have been achieved for rate 1/3 Turbo-codes with 4, 8 and 16-state constituent codes, respectively. Simulated error rate results for a block length of 1504 data bits (188 bytes,mpeg packet) show excellent flare performance.     

高误码率下Turbo码分量编码器快速识别算法

针对目前Turbo码中,分量编码器递归系统卷积码识别算法计算量大,容错性不好两大缺点,该文提出了一种容错性能较好的快速识别算法。首先,在分析递归系统卷积码特殊结构的基础上,定义了更具普遍意义的广义码重概念;其次,建立出递归系统卷积码生成多项式数据库,按照数据库中多项式是否为实际编码多项式的情况,分析出多项式所对应的结果向量广义码重概率分布;然后,按照分析出的广义码重概率分布,基于极大极小准则,导出快速识别算法判决门限的计算公式;最后通过遍历多项式数据库,将遍历的多项式所对应的校验方程广义码重值与判决门限比较,从而实现参数的快速识别。仿真结果表明:理论分析出的广义码重概率分布与仿真结果相一致,同时算法容错性能较好,在误码率高达0.09的条件下,各种编码约束长度下的递归系统卷积码识别率在90%以上,并且计算复杂度较小。