Pipelined Architectures for High-Speed and Area-Efficient Viterbi Decoders

Pipelined Architectures for High-Speed and Area-Efficient Viterbi Decoders Chen, Chao-Nan Chu, Hsi-Cheng Convolutional code Viterbi decoder In-place path metric updating Inserting pipeline levels into ACS Convolutional Codes Convolutional encoders map information streams into a long code sequence. k = 1 bit input blocks produce n = 2 code symbols each. The code rate k/n expresses the information per coded bit and the constraint length v defines the encoder memory order. This encoder has 2(v 1) = 4 states. 1st code symbol input output 2nd code symbol Fig.1 A simple rate , v = 3 convolutional encoder Viterbi Algorithm (VA) The most commonly employed decoding technique that can be implemented using either software or digital hardware. VA uses the trellis diagram (Fig.2) and can theoretically perform maximum likelihood decoding. It finds the most likely path by means of suitable distance metric between the received sequence and all the trellis paths. input bit 0 input bit 1 00 00 11 01 10 11 00 11 10 00 11 00 11 00 11 10 10

10 11 11 11 00 00 00 01 01 01 01 01 01 01 10 10 10 Fig.2 Trellis diagram representation of the encoder of Fig.1 Viterbi Decoder BMU: BM are computed from introduced input data ACSU: PMs of all states are updated according to equation (1) SMU: The stored decisions are employed in the SMU to build a unique decoded output PM[i](t+1) = allmin ( PM[k](t) + BM([k][i])(t) ) possible (1) PM[k](t) : Path metric corresponding to state k at instant t BM([k][i])(t): Branch metric of the transtion from state k at t to state i at t+1 Input Branch Metric Unit (BMU) ACS Unit Survior-Path Memory Unit (SMU) Fig.3 Basic computation units in Viterbi decoder Output In-place Path Metric Updating State i Efficiently save half memory size State i+2v-1

State 2i State 2i+1 Overwrites previous metric of state i Overwrites previous metric of state i+2v-1 Fig. 3. Partial trellis diagram or butterfly for in-place computation of updated path metrics. State 0 1 2 3 4 5 6 7 (a) State 0 1 2 3 4 5 6 7 State 0 1 2 3 4 5 6 7 State 0 2 4 6 1 3 5 7 (b)

State 0 4 1 5 2 6 3 7 Fig. 4. Example for v=3: (a) butterflies in the traditional approach; (b) states and butterfies during one full cycle of in-place computation State 0 1 2 3 4 5 6 7 State i State 2i State i+32 State 2i+1 Figure 5. The diagram of BF unit Table 1. State arrangement and path metric updating for constraint length 7 (64 states) Figure 6. A novel architecture for the Viterbi decoder Table 2. Address scrambling of path metric memory for constraint length 7 (64 states) Cycle 0 1 2 3 Iterarion 4 5 6

7 0 Address(DpRAM0-3) 0 1 2 3 4 5 6 7 Address(DpRAM4-7) 0 1 2 3 4 5 6 7 Iteration 1 Address(DpRAM0-3) 0 2 4 6 1 3 5 7 Address(DpRAM4-7)

1 3 5 7 0 2 4 6 State i State 2i State i+32 State 2i+1 Figure 5. The diagram of BF unit Table 1. State arrangement and path metric updating for constraint length 7 (64 states) Figure 6. A novel architecture for the Viterbi decoder Table 2. Address scrambling of path metric memory for constraint length 7 (64 states) Cycle 0 1 2 3 Iterarion 4 5 6 7 0 Address(DpRAM0-3) 0

1 2 3 4 5 6 7 Address(DpRAM4-7) 0 1 2 3 4 5 6 7 Iteration 1 Address(DpRAM0-3) 0 2 4 6 1 3 5 7 Address(DpRAM4-7) 1 3 5 7 0 2

4 6 State i State 2i State i+32 State 2i+1 Figure 5. The diagram of BF unit Table 1. State arrangement and path metric updating for constraint length 7 (64 states) Figure 6. A novel architecture for the Viterbi decoder Table 2. Address scrambling of path metric memory for constraint length 7 (64 states) Cycle 0 1 2 3 Iterarion 4 5 6 7 0 Address(DpRAM0-3) 0 1 2 3 4 5 6

7 Address(DpRAM4-7) 0 1 2 3 4 5 6 7 Iteration 1 Address(DpRAM0-3) 0 2 4 6 1 3 5 7 Address(DpRAM4-7) 1 3 5 7 0 2 4 6 State i State

2i State i+32 State 2i+1 Figure 5. The diagram of BF unit Table 1. State arrangement and path metric updating for constraint length 7 (64 states) Figure 6. A novel architecture for the Viterbi decoder Table 2. Address scrambling of path metric memory for constraint length 7 (64 states) Cycle 0 1 2 3 Iterarion 4 5 6 7 0 Address(DpRAM0-3) 0 1 2 3 4 5 6 7 Address(DpRAM4-7) 0 1

2 3 4 5 6 7 Iteration 1 Address(DpRAM0-3) 0 2 4 6 1 3 5 7 Address(DpRAM4-7) 1 3 5 7 0 2 4 6 Insert Pipeline Levels into ACS Generally, the maximum number of ACS pipeline levels is only dependent on the ratio N/P (N: number of states ; P: number of ACS unit) Table 3. The maximum pipelines levels for (N/P) from 1 to 64 N/P 1 2 4

8 16 32 64 ACS pipline levels 1 1 2 5 10 20 40 Figure 7. A simple example of inserting pipeline levels into ACS unit PM[k](t) BM[k][i](t) + Comparator PM[j](t) BM[j][i](t) + Selector PM[i](t+1) Conclusion Assuming pipeline levels are equally distributed into ACS, the decoding speed is LP/N 5/8 of a state-parallel ACS instead of P/N. The maximum possible area-saving can be obtained by selecting a large enough ratio N/P A favorable solution for applications, where area-saving and hence power, is the most crucial while moderate decoding speed degradation is allowed.

Recently Viewed Presentations

  • Lecture #11 Date

    Lecture #11 Date

    Lecture Date _____ Chapter 24 ~ The Origin of Species Macroevolution: the origin of new taxonomic groups Speciation: the origin of new species Anagenesis (phyletic evolution): accumulation of heritable changes Cladogenesis (branching evolution): budding of new species from a parent...
  • 4 - Midland Independent School District / Overview

    4 - Midland Independent School District / Overview

    An element is a substance that contains only one kind of atom. ... Atoms that are not stable will share or transfer electrons from another atom. Each column, or group, in the periodic table has the same number of electrons...
  • Precipitation Titration Analyte is titrated with a standard

    Precipitation Titration Analyte is titrated with a standard

    · Volhard titration - formation of a soluble, colored complex at the end point. · Fajans titration - adsorption of a colored indicator on the precipitate at the end point. Mohr method The Mohr method was first published in 1855...
  • How successful was the First Five Year Plan?

    How successful was the First Five Year Plan?

    The Five Year Plan 1953-1957. By 1953, inflation had been reduced to 15% and the government was in complete control of industry. Mao also benefitted from the 'National Resources Committee' (NRC) which had been established by the KMT. 200,000 managers...
  • Foodchains - Teaching and Learning Resources

    Foodchains - Teaching and Learning Resources

    Clip-art is royalty-free from Microsoft and Printmaster Gold What is an ecosystem? An ecosystem refers to all the animals and plants found in one place, and the way they all live together.
  • Norms in criminal organizations: Inside the evolution of ...

    Norms in criminal organizations: Inside the evolution of ...

    Enforcement of legal norms by the state: no vigilant justice . Criminal organizations . Absence of state monopoly of violence. Norm enforcement cannot be delegated to third party (i.e. state) Lab for studying the evolution of social order
  • The FFA Emblem Objectives  Identify six parts of

    The FFA Emblem Objectives Identify six parts of

    The FFA Emblem Objectives Identify six parts of the FFA emblem. Describe the meaning of each part. Objectives Identify six parts of the FFA emblem.
  • Antigone - Ms. Christina Baumeister

    Antigone - Ms. Christina Baumeister

    Antigone Day 2: Sit in your Sticker Groups. SWBAT: Understand the importance of vocabulary and complete a vocabulary assignment after they complete an ACT cold read assessment.