Vol. 60 n°1-2, January-February 2005

Turbo codes

 

Guest editors :  Ramesh PYNDIAH* and Michel JézéQUEL*

GET/Telecom Bretagne - Brest - France

 

 

Distance upper bounds and true minimum distance results for Turbo-Codes designed with DRP interleavers

Stewart CROZIER*, Paul GUINAND*

* Communications Research Centre; 3701 Carling Ave., P.O. Box 11490, Station H; Ottawa, Canada, K2H 8S2

 

Abstract: 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.

 

Key words: Error correcting code, Convolutional code, Turbo code, Code distance, Minimal distance, Upper bound, Interleaving, Punctured code.

 

 

Marker codes for channels with insertions and deletions

Edward A. RATZER*

* Inference Group, Cavendish Laboratory, University of Cambridge, Cambridge CB3 0HE, UK

 

Abstract: Coding for channels with synchronization errors is studied. Marker codes, each consisting of a low-density parity-check code with inserted markers, are developed. At low insertion- deletion probabilities marker codes are shown to outperform watermark codes. Full iterative decoding enhances performance to close to the capacity bounds. The low-density parity-check codes are optimized and the best known rate R = 0.5 code for the insertiondeletion channel presented. The codes are also shown to be effective on the bit-deletion channel.

 

Key words: Error correcting code, Transmission error, Synchronization, Parity check, Signal flip, Sparse matrix.

 

 

Advanced decoding algorithms for Reed-Solomon/Convolutional concatenated codes

Meritxell LAMARCA*, Josep SALA*, Alfonso MARTINEZ**

* Dept. of Signal Theory and Communications, Universitat Politècnica de Catalunya; UPC Campus Nord- Mòdul D5, c/Jordi Girona, 1-3, 08034 Barcelona, Spain

** Dept. Electrical Engineering, Signal Processing Group (SPS), Technische Universiteit Eindhoven; Dept.

Electrical Engineering - Signal Processing Group (SPS); Den Dolen 2, P.O. Box 513, 5600 MB Eindhoven, The Netherlands; Email: alfonso.martinez at ieee.org. Formerly with the European Space Agency (ESA), European Research and Technology Centre (ESTEC), in Noordwijk, The Netherlands.

 

Abstract: The evaluation of the union bound for the BER of Reed-Solomon/Convolutional concatenated codes indicates that their performance might largely improve through the application of soft iterative decoders. This paper presents an iterative decoding algorithm for concatenated codes consisting of an outer Reed-Solomon code, a symbol interleaver and an inner convolutional code. The performance improvement for iterative and non-iterative decoders is evaluated. Existing solutions for the different decoding stages and their interfaces are discussed and their performance is compared. A new procedure is proposed to define the feedback signal from the output of the Reed-Solomon decoder to the input of the convolutional decoder, which captures the reliability information that can be inferred from errors-and-erasures RS decoders and includes the "state pinning" approach as a particular case. The decoding schemes are applied to the specific DVB-S concatenated code.

 

Key words: Error correcting code, Decoding, Concatenation, Convolutional code, Reed Salomon code, Iteration, Upper bound, Digital television.

 

 

On Multiple Slice Turbo Codes

David GNAEDIG1, 2, 3, Emmanuel BOUTILLON2, Michel JÉZÉQUEL3, Vincent C. GAUDET4, P. Glenn GULAK5

1. TurboConcept - Technopôle Brest-Iroise - 115 rue Claude Chappe - 29280 Plouzané - France.

2. LESTER-Université de Bretagne Sud - BP 92116 - 56321 Lorient Cedex - France.

3. GET/ENST Bretagne/PRACOM - Unité CNRS 2658 - BP 832 - 29285 Brest Cedex France.

4. Dept. of ECE-University of Alberta - Edmonton, Alberta - Canada T6G 2V4.

5. Dept. of ECE - University of Toronto - 10 King's College Road - Toronto, Ontario - Canada M5S 3G4.

 

Abstract: The main problem with the hardware implementation of turbo codes is the lack of parallelism in the MAP-based decoding algorithm. This paper proposes to overcome this problem by using a new family of turbo codes called Multiple Slice Turbo Codes. This family is based on two ideas: the encoding of each dimension with P independent tail-biting codes and a constrained interleaver structure that allows the parallel decoding of the P independent codewords in each dimension. The optimization of the interleaver is described. A high degree of parallelism is obtained with equivalent or better performance than the DVB-RCS turbo code. For very high throughput applications, the parallel architecture decreases both decoding latency and hardware complexity compared to the classical serial architecture, which requires memory duplication.

Key words: Error correcting code, Turbo code, Decoding, Convolutional code, Parallelism, Interleaving, Recursivity, A posteriori probability.

 

 

Time-invariant and switch-type hybrid iterative decoding of low-density parity-check codes

Pirouz ZARRINKHAT*, Amir H. BANIHASHEMI*, Hua XIAO*

*Broadband Communications and Wireless Systems (BCWS) Centre, Department of Systems and Computer Engineering, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, Canada K1S 5B6.

 

Abstract: Hybrid decoding is to combine different iterative decoding algorithms with the aim of improving error performance or decoding complexity. This, e.g., can be performed by using a specific blend of different algorithms in every iteration (time-invariant hybrid: HTI), or by switching between different algorithms throughout the iteration process (switch-type hybrid: HST). In this work, we study HTI and HST algorithms both asymptotically, using densityevolution,

and at finite block lengths, using simulations, and show that these algorithms perform considerably better than their constituent algorithms. We also investigate the convergence properties of HTI and HST algorithms, under both the assumption of perfect knowledge of the channel, and the lack of it, and show that compared to HST algorithms, such as Gallager's algorithm B, HTI algorithms are far less sensitive to channel conditions and thus can be practically more attractive.

 

Key words: Error correcting code, Decoding, Iteration, Mixed method, Parity check, Turbo code, Sparse matrix, Invariance, Switched mode, Algorithm convergence.

 

 

Iterative reliability-based decoding in bandwidth efficient coding schemes

Motohiko ISAKA*, Marc FOSSORIER**

* Dept. of Informatics, Kwansei Gakuin University, 2-1 Gakuen, Sanda 6691337, Japan.

** Dept. of Electrical Engineering, University of Hawaii at Manoa, 2540 Dole st., Honolulu, HI 96822-2303, USA

 

Abstract: In this paper, we enhance and investigate the performance of some bandwidth efficient coding schemes with iteratively decodable structure and cycles in their graph representation. In particular, we deal with bit-interleaved coded modulation and transmit diversity, using low-density parity-check and turbo codes as component codes. Simulation results show that the suboptimality of iterative decoding for moderate length codes can be at least partially compensated. Hence they allow us to also measure partially this suboptimality.

 

 Key words: Error correcting code, Decoding, Reliability, Iteration, Interleaving, Code modulation, Diversity, Turbo code, Parity check, Sparse matrix, Rayleigh fading, Radio channel, Intersymbol interference.

 

 

 

Linear and widely linear filtering applied to iterative detection of generalized MIMO signals

Melanie WITZKE*

* Institute for Communications Engineering (LNT), Munich University of Technology (TUM), 80290 Munich, Germany

 

Abstract: To suppress the co-antenna interference in multiple input multiple output (MIMO) systems, an iterative receiver with a linear detector for complex symbols is investigated. We show that the considered generalized MIMO system, i.e., a system that transmits complex conjugate repetitions in addition to the pure data, requires the application of a widely linear (WL) detector. A WL detector consists of four real filters which are represented by two complex filters for the received signal and its complex conjugate, respectively. Furthermore, we present approximations of the detector that significantly reduce computational complexity with only little loss in frame-error rate performance. Simulation results show that the proposed MIMO system achieves large gains over standard solutions.

 

Key words: Linear filtering, Signal detection, Iteration, Multidimensional system, Complex number, Signal interference, Radiocommunication, Space-time processing.

 

 

Turbo soft combining hybrid ARQ techniques: Theory and application to 3G wireless networks

Francesco CHITI*, Romano FANTACCI*, Francesco VERSACI*

* Dipartimento di Elettronica e Telecomunicazioni - Università di Firenze, via di S. Marta 3, I-50139 Firenze, Italy.

 

Abstract: This paper deals with the application of Hybrid Automatic Repeat reQuest (H-ARQ) techniques to allow reliable data communications in wireless 3G networks. Basically, retransmission of coded data is endowed with soft combining schemes applied, respectively, to packet replicas, or to decoding algorithm outputs. In particular, the proposed coding scheme takes advantage of error correction capabilities of the turbo codes, while the combining algorithm follows the diversity approach. The performance of the proposed H-ARQ schemes has been derived by means of a suitable analytical approach and numerical simulations in the case of a typical UMTS environment. The results highlight the good behavior of the proposed scheme in term of error rate, throughput, packet delivery delay and power reduction.

 

Key words: Mobile radiocommunication, ARQ, UMTS, Turbo code, Throughput, Data communication, High rate, Error correcting code, Diversity, Fading, Mixed method.

 

 

 

Bounds on mutual information for simple codes using information combining

Ingmar LAND1, Simon HUETTINGER2, Peter A. HOEHER3, Johannes HUBER4

1. Ingmar Land was with the Information and Coding Theory Lab, Faculty of Engineering, University of Kiel, Kaiserstrasse 2, D-24143 Kiel, Germany. He is now with the Digital Communications Division, Department of Communication Technology, Aalborg University, Fredrik Bajers Vej 7, DK-9220 Aalborg, Denmark

2. Simon Huettinger was with the Institute for Information Transmission, University Erlangen-Nürnberg, Cauerstraße 7/LIT D-91058 Erlangen, Germany. He is now with Siemens AG, Germany

3. Peter A. Hoeher is with the Information and Coding Theory Lab, Faculty of Engineering, University of Kiel, Kaiserstrasse 2, D-24143 Kiel, Germany

4. Johannes Huber is with the Institute for Information Transmission, University Erlangen-Nürnberg, Cauerstraße 7/LIT, D-91058 Erlangen, Germany

 

Abstract: For coded transmission over a memoryless channel, two kinds of mutual information are considered: the mutual information between a code symbol and its noisy observation and the overall mutual information between encoder input and decoder output. The overall mutual information is interpreted as a combination of the mutual informations associated with the individual code symbols. Thus, exploiting code constraints in the decoding procedure is interpreted as combining mutual informations. For single parity check codes and repetition codes, we present bounds on the overall mutual information, which are based only on the mutual informations associated with the individual code symbols. Using these mutual information bounds, we compute bounds on extrinsic information transfer (EXIT) functions and bounds on information processing characteristics (IPC) for these codes.

 

Key words: Information theory, Information measure, Error correcting code, Concatenation, Iteration, Memoryless channel, Binary channel.