Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A New Efficient List Viterbi Decoder

IP.com Disclosure Number: IPCOM000126124D
Publication Date: 2005-Jul-01
Document File: 2 page(s) / 28K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a new algorithm that arranges strings in the form of a tree, resulting in a more efficient use of memory and computations than previous Viterbi list algorithms. Benefits include improved performance of a GSM/GPRS by up to 2.5 dB.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 58% of the total text.

A New Efficient List Viterbi Decoder

Disclosed is a method for a new algorithm that arranges strings in the form of a tree, resulting in a more efficient use of memory and computations than previous Viterbi list algorithms. Benefits include improved performance of a GSM/GPRS by up to 2.5 dB.

Background

The combination of cyclic redundancy check (CRC) protection bits with convolutional encoding appears in several communication standards, like the CS-2, 3 GSM, and MCS group of EGPRS standards. In the encoding phase, a block of N-n information bits is appended with n CRC bits, and then the N bits are passed through a convolutional encoder. On the receiving side, the usual procedure is to apply a Viterbi decoder that finds N bits. The decoded bits polynomial is divided by the CRC polynomial, and if the residue is zero then it is accepted as correct. Otherwise, the block is rejected. 

A way to improve this recognition rate is to apply a “Viterbi list” decoder, which results in a list of P decoded bit strings ordered by their likelihoods. The most likely string that is CRC-compliant is accepted, otherwise the block is rejected. However, Viterbi list algorithms can be expensive both in memory and in calculation.

General Description

The disclosed method is a Tree Extension Algorithm (TEA), and is a synthesis of two current types of algorithms: the List Extension Algorithm (LEA) and the Tree Trellis Algorithm (TTA).

The TEA is an improvement over the LEA in the following ways:

§...