Search and determination of convolutional self-doubly orthogonal codes for iterative threshold decoding

In this paper, we present new results on the search and determination of wide-sense convolutional self-doubly orthogonal codes (CSO/sup 2/C-WS) which can be decoded using a simple iterative threshold decoding algorithm without interleaving. For their iterative decoding, in order to ensure the independence of observables over the first two iterations without the presence of interleavers, these CSO/sup 2/C must satisfy specific orthogonal properties of their generator connections. The error performances of CSO/sup 2/C, depend essentially on the number of taps J of the code generators but not on the code memory length. Since the overall latency of the iterative threshold decoding process is proportional to the memory length of the codes, therefore, when searching for the best CSO/sup 2/C-WS of a given J value, the memory length of the codes should be chosen to be as small as possible. In this paper, we present a code-searching technique based on heuristic computer searching algorithms which have yielded the best known CSO/sup 2/C-WS. The construction method for CSO/sup 2/C-WS has provided the best known r=1/2 codes with the shortest memory length having J/spl les/30. Although not very complex to implement, the search method presented here is quite efficient especially in reducing very substantially the execution time required to determine the codes with the shortest spans. Furthermore, in addition to presenting the search results for the codes, error performances obtained by simulation are also provided.     

基于删余等效的高码率卷积码的低复杂度译码方法

根据删余卷积码具有较低的译码复杂度这一特征,提出了一种适用于普通高码率卷积码的低复杂度译码方法。通过多项式生成矩阵表示法,推导了删余卷积码的等效多项式生成矩阵,给出了等效多项式生成矩阵的计算准则。在分析删余卷积码与相同码率普通卷积码的等效关系和区别的基础上,提出了高码率卷积码的删余等效并给出了计算高码率卷积码删余等效后原始码和删余矩阵的方法。以原始码和删余矩阵构成的删余等效结构为译码基础,实现了高码率卷积码的低复杂度译码,其译码复杂度与原始码相当。仿真结果表明,删余等效译码方法相对于正常译码方法,其性能损失很小。     

Design and decoding of optimal high-rate convolutional codes

This correspondence deals with the design and decoding of high-rate convolutional codes. After proving that every (n,n-1) convolutional code can be reduced to a structure that concatenates a block encoder associated to the parallel edges with a convolutional encoder defining the trellis section, the results of an exhaustive search for the optimal (n,n-1) convolutional codes is presented through various tables of best high-rate codes. The search is also extended to find the "best" recursive systematic convolutional encoders to be used as component encoders of parallel concatenated "turbo" codes. A decoding algorithm working on the dual code is introduced (in both multiplicative and additive form), by showing that changing in a proper way the representation of the soft information passed between constituent decoders in the iterative decoding process, the soft-input soft-output (SISO) modules of the decoder based on the dual code become equal to those used for the original code. A new technique to terminate the code trellis that significantly reduces the rate loss induced by the addition of terminating bits is described. Finally, an inverse puncturing technique applied to the highest rate "mother" code to yield a sequence of almost optimal codes with decreasing rates is proposed. Simulation results applied to the case of parallel concatenated codes show the significant advantages of the newly found codes in terms of performance and decoding complexity.     

High-rate recursive convolutional codes for concatenated channel codes

This letter presents the results of the search for optimum punctured recursive convolutional codes (RCCs) of rate k/k+1, for k=2,...,8, suitable for concatenated channel codes whose constituent encoders are recursive, systematic convolutional codes. The mother codes that are punctured are rate-1/2 RCCs proposed for use in parallel and/or serial concatenation schemes. Extensive tables of systematic and nonsystematic puncturing patterns, optimized relative to various objective functions suitable for concatenated channel codes, are presented for several mother codes.     

New rate-compatible punctured convolutional codes for Viterbidecoding

New good rate-P/(P+δ) rate-compatible punctured convolutional (RCPC) codes for 2⩽P⩽7 and 1⩽δ⩽(n-1)P were found and tabulated, These codes have been determined by iterative search based upon a criterion of maximizing the free distance and were generated by periodically puncturing their rate-1/n mother codes of memory 2⩽M⩽6 and n=2. These codes are expected to find their applications in unequal error protection schemes employing Viterbi decoding     

Symbol-by-symbol MAP decoding algorithm for high-rate convolutionalcodes that use reciprocal dual codes

A symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes applying reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased. All requirements for iterative decoding schemes are fulfilled. Since tail-biting convolutional codes are equivalent to quasi-cyclic block codes, the decoding algorithm for truncated or terminated convolutional codes is modified to obtain a soft-in/soft-out decoder for high-rate quasi-cyclic block codes which also uses the dual code because of complexity reasons. Additionally, quasi-cyclic block codes are investigated as component codes for parallel concatenation. Simulation results obtained by iterative decoding are compared with union bounds for maximum likelihood decoding. The results of a search for high-rate quasi-cyclic block codes are given in the appendix     

An extensive search for good punctured rate-k/(k+1) recursive convolutional codes for serially concatenated convolutional codes

In many practical applications requiring variable-rate coding and/or high-rate coding for spectral efficiency, there is a need to employ high-rate convolutional codes (CC), either by themselves or in a parallel or serially concatenated scheme. For such applications, in order to keep the trellis complexity of the code constant and to permit the use of a simplified decoder that can accommodate multiple rates, a mother CC is punctured to obtain codes with a variety of rates. This correspondence presents the results of extensive search for optimal puncturing patterns for recursive convolutional codes leading to codes of rate k/(k+1) (k an integer) to be used in serially concatenated convolutional codes (SCCC). The code optimization is in the sense of minimizing the required signal-to-noise ratio (SNR) for two target bit-error rate (BER) and two target frame-error rate (FER) values. We provide extensive sample simulation results for rate-k/(k+1) SCCC codes employing our optimized punctured CC.     

Sphere-packing bounds for convolutional codes

We introduce general sphere-packing bounds for convolutional codes. These improve upon the Heller (1968) bound for high-rate convolutional codes. For example, based on the Heller bound, McEliece (1998) suggested that for a rate (n - 1)/n convolutional code of free distance 5 with /spl nu/ memory elements in its minimal encoder it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. A simple corollary of our bounds shows that in this case, n < 2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened. Note that the resulting bounds are also highly useful for codes of limited bit-oriented trellis complexity. Moreover, the results can be used in a constructive way in the sense that they can be used to facilitate efficient computer search for codes.     

A flexible rate slepian-wolf code construction

A flexible rate Slepian-Wolf (SW) code is constructed, which is vital for wireless sensor network applications. The proposed solution is based on an efficient and practical algorithm to compute the syndrome of the rate-compatible convolutional codes (RCPC). Using this algorithm, there is no need to compute the syndrome of punctured version of the mother code for each puncturing matrix, which is complex. Instead, the syndrome of the punctured code is the punctured version of the syndrome of the mother code using the same pattern of puncturing. The algorithm is general for all convolutional codes in Zq. The strategy is also generalized for parallel and serial concatenated convolutional codes. For the cases, where the dependencies among sources are modeled as a virtual discrete channel, a simplified decoding scheme is suggested. This method is generalized to achieve all points on the SW boundary using a simple code design technique. Simulation results demonstrate the performance and effectiveness of the proposed methods.     

A new approach to the construction of high-rate convolutional codes

This letter presents a new technique to construct high-rate convolutional codes using a structure formed by a high-rate block code and a simpler convolutional code. The goal is to obtain good convolutional codes in terms of free distance and number of nearest neighbors, with better performance than punctured codes. The obtained codes improve over the best known high-rate punctured codes with the same rate and memory in terms of both bit error probability and computational decoding complexity     

Design of efficiently encodable moderate-length high-rate irregular LDPC codes

This paper presents a new class of irregular low-density parity-check (LDPC) codes of moderate length (10/sup 3//spl les/n/spl les/10/sup 4/) and high rate (R/spl ges/3/4). Codes in this class admit low-complexity encoding and have lower error-rate floors than other irregular LDPC code-design approaches. It is also shown that this class of LDPC codes is equivalent to a class of systematic serial turbo codes and is an extension of irregular repeat-accumulate codes. A code design algorithm based on the combination of density evolution and differential evolution optimization with a modified cost function is presented. Moderate-length, high-rate codes with no error-rate floors down to a bit-error rate of 10/sup -9/ are presented. Although our focus is on moderate-length, high-rate codes, the proposed coding scheme is applicable to irregular LDPC codes with other lengths and rates.     

New very high rate punctured convolutional codes

New very high rate punctured convolutional codes suitable for Viterbi decoding are presented. These codes extend recent results on high rate convolutional codes by employing an efficient computer search technique and are optimum in that they minimise the residual bit error rate over all puncturing patterns given a particular basis code. Tables of new codes of rate (n-1)/n are given for n=9, 10, 11 and 12     

MAP decoding of convolutional codes using reciprocal dual codes

A new symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes using reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased for codes of rate greater than 1/2. The discussed algorithms fulfil all requirements for iterative (“turbo”) decoding schemes. Simulation results are presented for high-rate parallel concatenated convolutional codes (“turbo” codes) using an AWGN channel or a perfectly interleaved Rayleigh fading channel. It is shown that iterative decoding of high-rate codes results in high-gain, moderate-complexity coding     

Energy-efficient node position identification through payoff matrix and variability analysis

This paper investigates the use of punctured recursive systematic convolutional codes for turbo coding in a 2-user binary adder channel (2-BAC) in the presence of additive white Gaussian noise, aiming to achieve a higher transmission sum rate with reduced decoding complexity. The encoders for the 2-BAC are assumed to be block synchronized and to employ identical puncturing patterns. Iterative decoding combining the Bahl Cocke Jelinek Raviv algorithm and a two-user punctured trellis is employed. For each user and for a fixed puncturing pattern, random interleavers of length 256 bits or 1024 bits, respectively, are simulated and corresponding curves relating bit error rate versus signal to noise ratio are presented for performance comparison purposes. Computer simulation indicates that the loss in performance of a punctured turbo code can be negligible when longer interleavers are used for both users, similarly to the single user case.     

On the computation of weight enumerators for convolutional codes

Performance bounds for maximum-likelihood decoding of convolutional codes over memoryless channels are commonly measured using the distance weight enumerator T(x,y), also referred to as the transfer function, of the code. This paper presents an efficient iterative method to obtain T(x,y) called the state reduction algorithm. The algorithm is a systematic technique to simplify signal flow graphs that algebraically manipulate the symbolic adjacency matrix associated with the convolutional code. Next, the algorithm is modified to compute the first few terms of the series expansion of T(1,y) and {/spl part/T(x,y)//spl part/x}/sub x=1/ (the distance spectra) without first computing the complete T(x,y).     

Reduced-state representations for trellis codes using constellation symmetry

This paper presents a symmetry-based technique for trellis-code state-diagram reduction that has more general applicability than the quasi-regularity technique of Rouanne et al. and Zehavi et al. for trellis codes using standard constellations and labelings. For a 2/sup /spl nu/x/-state trellis code, the new technique reduces the 2/sup 2/spl nu/x/ state diagram to 2/sup /spl nu/x+/spl nu/q/-state diagram where 0/spl les//spl nu//sub q//spl les//spl nu//sub x/. The particular value of /spl nu//sub q/ depends on the constellation labeling and the convolutional encoder. For standard rate-k/(k+1) set-partitioned trellis codes, /spl nu//sub q/=0, and the overall number of states is the same with the new technique as with quasi-regularity. For codes that are not quasi-regular (and thus not amenable to the quasi-regularity technique), the new technique often provides some improvement (when /spl nu//sub q/相似文献   

High-Rate Punctured Convolutional Codes for Soft Decision Viterbi Decoding

The high-rate punctured codes of rates 2/3 through 13/14 are derived from rate 1/2 specific convolutional codes with maximal free distance. Coding gains of derived codes are compared based on their bit error rate performances under soft decision Viterbi decoding.     

High-rate punctured convolutional codes: structure properties andconstruction technique

The authors present some properties of punctured convolutional codes, providing a construction method and a list of new, good, high-rate, long-memory punctured codes. The structure of punctured codes is examined and an upper bound on the free distance of punctured codes is derived, indicating that punctured codes are good codes. A construction method that generates the low-rate original codes which duplicate given known high-rate codes through perforation is proposed. Tables of punctured codes that duplicate the best known nonsystematic codes of rates 2/3 and 3/4 with memory lengths ranging from 3 to 23 and from 3 to 9, respectively, are given, together with the best known systematic codes for rates ranging from 2/3 to 7/8 with very long memory, M=44 through 48     

High-rate punctured convolutional codes for Viterbi and sequentialdecoding

An investigation is conducted of the high-rate punctured convolutional codes suitable for Viterbi and sequential decoding. Results on known short-memory codes M⩽8 discovered by others are extended. Weight spectra and upper bounds on the bit error probability of the best known punctured codes having memory 2⩽M ⩽8, and coding rates 2/3⩽R⩽7/8 are provided. Newly discovered rate-2/3 and -3/4 long-memory punctured convolutional codes with 9⩽M⩽23 are provided together with the leading terms of their weight spectra and their bit error performance bounds. Some results of simulation with sequential decoding are given     

BER analysis of convolution coded QDPSK, in digital mobile radio

The bit error rate (BER) performance of convolutional coded quaternary differential phase-shift keying (QDPSK) with Viterbi decoding is theoretically investigated in Rayleigh fading environments. The probability density functions of the path and branch metric values of Viterbi decoding are derived. The BERs after decoding due to additive white Gaussian noise and cochannel interference are theoretically analyzed. Rate 1/2 codes and their symbol punctured high-rate codes are considered, and the symbol positions for deletion to minimize the BER after decoding are presented for the codes with a constraint length K=3-7. It is shown that Viterbi decoding considerably reduces the desired signal-to-interference power ratio as well as the signal energy per information bit-to-noise power spectrum density ratio necessary to achieve a certain BER. The spectrum efficiency of the cellular mobile radio system, achievable by the use of the symbol punctured codes, is also evaluated