Browse Prior Art Database

HIGH-SPEED PARALLEL TURBO DECODING FOR MAX-LOG-MAP KERNEL OPERATION ALGORITHM

IP.com Disclosure Number: IPCOM000004632D
Original Publication Date: 2001-Mar-02
Included in the Prior Art Database: 2001-Mar-02
Document File: 4 page(s) / 33K

Publishing Venue

Motorola

Related People

Jun Ma: AUTHOR [+2]

Abstract

Optimal (MAP or log-MAP) decoding of the constituent codes in turbo decoding is prohibited by its intensive computational complexity for high data rate systems. Sub-optimal algorithms such as max-log-MAP are widely adapted due to their low computational complexity. Although parallelism can be explored across the trellis states, throughput is limited by the number of states in the forward and backward recursive computations of the state metric parameters alpha k (or beta k). In this paper, a novel look-ahead transformation based parallel turbo decoding architecture is proposed for the max-log-MAP algorithm. The resulting parallel architecture is achieved at the cost of additional computational complexity. VLSI architectures for both application specific and programmable implementations are considered. Novel instructions are proposed for high-speed turbo decoding on SIMD type application processors.

This text was extracted from a WORD97 document.
This is the abbreviated version, containing approximately 25% of the total text.

HIGH-SPEED PARALLEL TURBO DECODING FOR MAX-LOG-MAP KERNEL OPERATION ALGORITHM

Jun Ma* and Ali Saidi

[Note: The accompanying PDF contains the full document, including equations and figures that are not present in this file of searchable text.]

ABSTRACT

Optimal (MAP or log-MAP) decoding of the constituent codes in turbo decoding is prohibited by its intensive computational complexity for high data rate systems. Sub-optimal algorithms such as max-log-MAP are widely adapted due to their low computational complexity. Although parallelism can be explored across the trellis states, throughput is limited by the number of states in the forward and backward recursive computations of the state metric parameters alphak (or betak).ยท In this paper, a novel look-ahead transformation based parallel turbo decoding architecture is proposed for the max-log-MAP algorithm. The resulting parallel architecture is achieved at the cost of additional computational complexity. VLSI architectures for both application specific and programmable implementations are considered. Novel instructions are proposed for high-speed turbo decoding on SIMD type application processors.

1. INTRODUCTION

The MAP decoder [1][2] takes a received vector of soft values y and computes log-likelihood ratios, Lk, for each possible information bit mk,

(see accompanying PDF for equation)

The probability P(s', s, y) can be broken up into a product of three probabilities: (see accompanying PDF for equations) where s' and s represent the states in consecutive time steps. The parameters alphak and betak are calculated through forward and backward recursions on the code trellis, each of which also involves sums of products of probabilities.

Implementing the MAP algorithm in the log domain leads to the so called log-MAP algorithm, which converts the products into sums but transforms the additions into a relatively complicated log-add function

(see accompanying PDF for equation)

The log-add function, In(ex ey), is the kernel operation of the log-MAP decoder that dominates the overall turbo decoder complexity. It can be represented as the sum of a max operation and a correction term. The sum is usually also denoted as a max* operation.

(see accompanying PDF for equation)

The sub-optimal log-MAP with the correction term omitted, known as the max-log-MAP (i.e., max instead of max*), causes a performance degradation of 0.3 to 0.5 dB.

The computation of the parameters alphak and betak using max-log-MAP algorithm is given as

(see accompanying PDF for equation)

where i, j, l are state indices. From (5), it is seen that at time instance k 1, alphak+1 cannot be computed unless alphaks at time instance k have been computed. This recursion limits the throughput of the turbo decoding operations to the number of states in the trellis. Similar constraint in the betak computation limits t...