[go: up one dir, main page]

WO1996002973A1 - Unite acs viterbi possedant un circuit de renormalisation - Google Patents

Unite acs viterbi possedant un circuit de renormalisation Download PDF

Info

Publication number
WO1996002973A1
WO1996002973A1 PCT/US1994/007957 US9407957W WO9602973A1 WO 1996002973 A1 WO1996002973 A1 WO 1996002973A1 US 9407957 W US9407957 W US 9407957W WO 9602973 A1 WO9602973 A1 WO 9602973A1
Authority
WO
WIPO (PCT)
Prior art keywords
metrics
scale factor
acs
stored
metric
Prior art date
Application number
PCT/US1994/007957
Other languages
English (en)
Inventor
Hatch Graham
Christine Nguyen
Original Assignee
Stanford Telecommunications, Inc.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority to US08/038,323 priority Critical patent/US5349608A/en
Priority claimed from US08/038,323 external-priority patent/US5349608A/en
Application filed by Stanford Telecommunications, Inc. filed Critical Stanford Telecommunications, Inc.
Priority to PCT/US1994/007957 priority patent/WO1996002973A1/fr
Publication of WO1996002973A1 publication Critical patent/WO1996002973A1/fr

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6502—Reduction of hardware complexity or efficient processing
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
    • H03M13/4107—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing add, compare, select [ACS] operations

Definitions

  • This invention relates generally to signal decoders for decoding sequence codes such as the Viterbi algorithm decoder, and more particularly the invention relates to the add-compare-select (ACS) function processor in such decoders and the renormalization or rescaling of calculated path metrics in the ACS processor.
  • ACS add-compare-select
  • Convolutional encoding and Viterbi decoding are used to provide forward error correction in transmitted digital data and thus improve digital communication performance over a noisy transmission link.
  • the convolutional encoder establishes a code tree relationship between input and output sequences.
  • Each branch of the tree represents a single input symbol. Any input sequence traces out a specific path through the tree. Another way of viewing the code tree is the trellis diagram.
  • the Viterbi algorithm attempts to find a path through the trellis using the maximum likelihood decision. The two paths entering each node of a trellis are compared, and the path with the best metric (minimum error) is selected. The other path is rejected since its likelihood can never exceed that of the selected path regardless of the subsequent received data.
  • Fig. 1 is a block diagram of a Viterbi decoder and includes a branch metric unit (BMU) to calculate transition metrics ⁇ which are then accumulated recursively as path metrics in the add-compare-select (ACSU).
  • BMU branch metric unit
  • STU survivor trace unit
  • a high-speed Viterbi decoder implementation requires high-speed solutions for all three units. Since the BMU and STU are of simple feed forward structure, parallel processing architectures are easily
  • each ACS element includes two adders, a comparator, and a storage element. The two adders are used to add the values of the current state metrics to the new branch metrics for the upper and lower branches. The comparator then
  • the present invention is directed to efficiently maintaining the effective cumulative metric range by
  • an ACS processor in a Viterbi or sequence code decoder includes renormalization to rescale all path metrics when the minimum metric value exceeds a predetermined threshold.
  • pipelining is utilized to weigh the metric values in one bit cycle and renormalize the metric values as necessary in the succeeding bit cycle. Increased data rate and throughput are realized in the two cycle operation.
  • the cumulative path metrics are 6 bits wide (64 levels of quantization).
  • Fig. 1 is a functional block diagram of a Viterbi decoder.
  • Fig. 2 is an example of a four-state trellis in decoding a Viterbi algorithm.
  • Fig. 3 is a block diagram of an add-compare-select
  • Fig. 4 is a functional block diagram of an ACS unit in the processor of Fig. 3.
  • Fig. 5 is a functional block diagram of
  • ACS add-compare-select
  • VA Viterbi algorithm
  • Underlying the algorithm is a discrete-time Markov chain with a finite number of N states s i .
  • T a transition takes place from the state at time kT to the new state at time (k + 1)T.
  • the transition probabilities depend on the state at time k, but are independent of the previous history of the process (Markov property).
  • the VA recursively estimates the path the Markov process has taken through the trellis (sequence estimation). At each new time instant k and for every state, the VA
  • ⁇ i,k a probability measure called the path metric ⁇ i,k for each state s i at every time instant k.
  • a transition metric ⁇ ij, k is calculated for all possible transition branches from state s j to state s i (s j ⁇ s i ) of the trellis.
  • Viterbi processor can be divided into the three basic units as shown in Fig. 1.
  • the input data are used in the transition metric unit (TMU) to calculate the transition metrics ⁇ ij , which then are accumulated recursively as path metrics ⁇ i in the add-compare-select unit (ACSU).
  • the survivor memory unit (SMU) processes the decisions made in the TMU and ACSU and outputs the estimated data.
  • the ACS contains the most critical path which determines the speed of the decoder.
  • a critical aspect in the ACS is rescaling of all path metrics so that the full scale range of the ACS processor is not exceeded.
  • Fig. 3 is a functional block diagram of an ACS processor in accordance with one embodiment of the invention which uses 64 ACS elements in parallel at a maximum speed of 45 MHz to update the path metrics.
  • the current metrics value (cm0x) and a decimated value (cm0x-32) are applied to multiplexer 10
  • the current metrics value (cm1x) and a decimated value (cm1x-32) are applied to
  • the current values are selected as outputs except when a renormalization signal is applied to the
  • multiplexers The multiplexer outputs are applied through registers 13, 14 to adders 16, 18 which add the current metrics values to the branch metrics values (br0x, br1x). Comparator 20 and multiplexer 22 then select the lesser cumulative metrics value of adders 16, 18 as the output of multiplexer 22, which is applied to a register 50 in Fig. 5.
  • the two adders are used to add the values of the current state metrics to the new incoming branch metrics for the upper and lower branches at a node.
  • the comparator then evaluates results of the two adders and selects the smaller of the two metrics.
  • the complexity of this circuit is linearly proportional to the number of bits used to represent the path metrics.
  • a 3-bit soft decision input data (8 levels of quantization) with non-uniform metric assignment is provided to give 3-bit branch metrics.
  • the cumulative path metrics are 6 bits wide whereby the value of any path metric is limited to the value "63" when it exceeds the 6-bit range.
  • renormalization is utilized to rescale all of the path metrics when the minimum metric value exceeds a predetermined threshold.
  • the purpose of this function is to ensure a minimum effective cumulative metric range between the largest metric and the smallest metric.
  • renormalization is done by subtracting the value "32" when the smallest metric is greater than "31".
  • the threshold of "32" is chosen because it takes minimum hardware and time to perform the subtraction and also that value will give a dynamic cumulative metric range of 31 units, which has been shown through simulations to be an adequate value.
  • Each register provides an output to the AND gate 52 when the value stored in the register exceeds 31.
  • the lifo cycle operation reduces circuit complexity and increases data throughput.
  • the ACS processor in accordance with the present invention, provides a simple yet powerful rescaling of metric values.
  • the ACS processor improves speed without any loss in performance since the dynamic cumulative metric range is not changed.

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)

Abstract

Décodeur Viterbi comprenant un organe de traitement (ACS0, ACS1, ...ACS63) à fonction ACS (ajouter-comparer-choisir), dont on augmente la vitesse sans perte de ses performances en maintenant une plage de mesures cumulatives dynamiques pour les mesures calculées afin d'obtenir deux mesures calculées dont la plus petite est mémorisée avec les mesures d'états logiques précédemment calculées. Dans le circuit de renormalisation (RENORM), les mesures d'états logiques mémorisées sont comparées avec un facteur d'échelle choisi, par exemple un demi facteur d'échelle maximum, et toutes les mesures d'états logiques en vigueur sont remises à l'échelle lorsque la valeur des mesures mémorisées dépasse le facteur d'échelle choisi.
PCT/US1994/007957 1993-03-29 1994-07-15 Unite acs viterbi possedant un circuit de renormalisation WO1996002973A1 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US08/038,323 US5349608A (en) 1993-03-29 1993-03-29 Viterbi ACS unit with renormalization
PCT/US1994/007957 WO1996002973A1 (fr) 1993-03-29 1994-07-15 Unite acs viterbi possedant un circuit de renormalisation

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/038,323 US5349608A (en) 1993-03-29 1993-03-29 Viterbi ACS unit with renormalization
PCT/US1994/007957 WO1996002973A1 (fr) 1993-03-29 1994-07-15 Unite acs viterbi possedant un circuit de renormalisation

Publications (1)

Publication Number Publication Date
WO1996002973A1 true WO1996002973A1 (fr) 1996-02-01

Family

ID=26715077

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1994/007957 WO1996002973A1 (fr) 1993-03-29 1994-07-15 Unite acs viterbi possedant un circuit de renormalisation

Country Status (1)

Country Link
WO (1) WO1996002973A1 (fr)

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4823346A (en) * 1986-04-16 1989-04-18 Hitachi, Ltd. Maximum likelihood decoder
US5027374A (en) * 1990-03-26 1991-06-25 Motorola, Inc. Bit serial Viterbi decoder add/compare/select array
US5271042A (en) * 1989-10-13 1993-12-14 Motorola, Inc. Soft decision decoding with channel equalization
US5272727A (en) * 1991-05-29 1993-12-21 Nec Corporation Adaptive maximum likelihood sequence estimator using channel estimators of respective order of impulse response
US5280489A (en) * 1992-04-15 1994-01-18 International Business Machines Corporation Time-varying Viterbi detector for control of error event length
US5291524A (en) * 1991-11-21 1994-03-01 Sony Corporation Viterbi decoding apparatus
US5311557A (en) * 1992-07-10 1994-05-10 At&T Bell Laboratories Circular limiter for use in a receiver to reduce the effects of signal distortion

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4823346A (en) * 1986-04-16 1989-04-18 Hitachi, Ltd. Maximum likelihood decoder
US5271042A (en) * 1989-10-13 1993-12-14 Motorola, Inc. Soft decision decoding with channel equalization
US5027374A (en) * 1990-03-26 1991-06-25 Motorola, Inc. Bit serial Viterbi decoder add/compare/select array
US5272727A (en) * 1991-05-29 1993-12-21 Nec Corporation Adaptive maximum likelihood sequence estimator using channel estimators of respective order of impulse response
US5291524A (en) * 1991-11-21 1994-03-01 Sony Corporation Viterbi decoding apparatus
US5280489A (en) * 1992-04-15 1994-01-18 International Business Machines Corporation Time-varying Viterbi detector for control of error event length
US5311557A (en) * 1992-07-10 1994-05-10 At&T Bell Laboratories Circular limiter for use in a receiver to reduce the effects of signal distortion

Similar Documents

Publication Publication Date Title
US5349608A (en) Viterbi ACS unit with renormalization
US5027374A (en) Bit serial Viterbi decoder add/compare/select array
US5406570A (en) Method for a maximum likelihood decoding of a convolutional code with decision weighting, and corresponding decoder
US6697443B1 (en) Component decoder and method thereof in mobile communication system
US4583078A (en) Serial Viterbi decoder
KR100580160B1 (ko) 변형된 역추적 방식의 2단 연출력 비터비 알고리즘 복호화기
US6680986B1 (en) Method for implementing shared channel decoder for onboard processing satellites
CA2068117C (fr) Decodeur de viterbi
US4811346A (en) Process for the decoding of a convolutional code and corresponding decoder
US20070113161A1 (en) Cascaded radix architecture for high-speed viterbi decoder
CN101145790B (zh) 译码器、相加-比较-选择单元和其方法
CN100413217C (zh) 一种维特比译码器及用于维特比译码器的加比选单元电路
US20040122883A1 (en) High speed add-compare-select circuit for radix-4 Viterbi decoder
FI100564B (fi) Menetelmä transitiometriikan muodostamiseksi ja solukkoradiojärjestelm än vastaanotin
Chandel et al. Viterbi decoder plain sailing design for TCM decoders
WO1996002973A1 (fr) Unite acs viterbi possedant un circuit de renormalisation
El-Dib et al. Memoryless viterbi decoder
JP2614524B2 (ja) 誤り訂正符号の復号方法
KR101134806B1 (ko) 부호 복호 방법
US20040117721A1 (en) Pipelined add-compare-select circuits and methods, and applications thereof
KR100531840B1 (ko) 비터비 디코더의 가지 메트릭 계산 방법 및 그 회로
JP2003258650A (ja) 最尤復号器
KR0169777B1 (ko) 고속 비터비 복호기의 구현을 위한 정규화 방법 및 장치
US20040153958A1 (en) Path metric calculation circuit in viterbi decoders
Soumya Viterbi Decoder Plain Sailing Design for TCM Decoders

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
122 Ep: pct application non-entry in european phase
712F Gb: determination of foreign entitlement (section 12(1)/1977)
712G Gb: determination of foreign entitlement (sect. 12(1)/1977) withdrawn