On a Viterbi decoder design for low power dissipation

Contents

1  Introduction.  ...................................................................................................................  1

2  Viterbi  decoding  algorithm  and  low  power  techniques...................................................  4

2.1  Overview  and  introduction................................................................................  4

2.2  Convolutional  codes.  ........................................................................................  4

2.3  Viterbi  decoding  algorithm  ...............................................................................  8

2.4  Implementation  of  a  Viterbi  decoder.  .............................................................  11

2.5  Low-power  design  techniques.........................................................................  18

2.6  Review  of  previous  work  on  Viterbi  decoder  design.  ....................................  20

3  Proposed  Viterbi  decoder  design.  .................................................................................  22

3.1  Overview.  ........................................................................................................  22

3.2  General  Viterbi  decoder.  ................................................................................  22

3.3  Viterbi  encoder.  ..............................................................................................  24

3.4  Implementation  of  a  Viterbi  decoder.  .............................................................  25

3.4.1  Butterfly  block.  ................................................................................  26

3.4.2  Survivor  path  storage  module.  .........................................................  28

3.4.3  Decoded  output  sequence  generation  block.  ...................................  30

3.5  Proposed  low-power  design.  ..........................................................................  31

3.5.1  Survivor  path  storage  module...........................................................  31

3.5.2  Traceback  module.  ...........................................................................  32

3.5.3  Traceback  versus  register-exchange  approaches  in  power

efficiency.  .................................................................................................  34

3.5.4  Shift  register  versus  multiplexer  approach  in  power  efficiency.  .....  34

3.6  Design  for  testability  for  the  proposed  low-power  design.  ............................  35

3.7  Overall  design  flow.  .......................................................................................  36

4  Experimental  results.  ....................................................................................................  39

4.1  Environment.  ..................................................................................................  39

4.2  Power  dissipation  in  Viterbi  decoders.  ...........................................................  41

4.3  Low-power  Viterbi  decoders.  .........................................................................  43

4.3.1  Toggle  filtering  for  output  sequence  generation  block.  ..................  43

4.3.2  Replacement  of  the  shift  register  module  with  multiplexer.  ...........  44

4.3.3  Clock  gating.  ...................................................................................  45

5  Summary  ......................................................................................................................  48

Bibliography.  ....................................................................................................................  50

A  Software  documentation.  (VHDL  files)  ......................................................................  55

A.1  Encoder  module  (lenc.vhd)  ...............................................................................  55

A.2  Buffer  module  (lbuf.vhd)....................................................................................  56

A.3  Noise  module  (lnoise.vhd)..................................................................................  57

A.4  ACS  module  (0.vhd)...........................................................................................  58

A.5  ACS  module  (1.vhd)...........................................................................................  61

A.6  ACS  module  (2.vhd)...........................................................................................  64

A.7  ACS  module  (3.vhd)...........................................................................................  67

A.8  ACS  module  (4.vhd)...........................................................................................  70

A.9  ACS  module  (5.vhd)...........................................................................................  73

A.10  ACS  module  (6.vhd)...........................................................................................  76

A.11  ACS  module  (7.vhd)...........................................................................................  79

A.12  Register-exchange  module  (lftrace.vhd)  ............................................................  82

A.13  Selective  update  store  and  traceback  module  (ltrace_sel.vhd)..........................  85

A.14  Shift  update  store  and  traceback  module  (ltrace_shf.vhd)  .................................  89

A.15  Selective  update  store  and  traceback  module  with  low-power  considerations

(ltrace_selw.vhd)  .........................................................................................................  93

A.16  Shift  register  module  with  multiplexer  method  (lshf.vhd)  .................................  97

A.17  Shift  register  module  (lshift.vhd)  .......................................................................  99

A.18  Counter  module  (lcount.vhd)............................................................................  100

A.19  Top  level  interconnection  module  (ltop.vhd)  ...................................................  102

A.17  Test  bench  for  the  top  level  (ltb_top.vhd)  .......................................................  109

Vita.  ................................................................................................................................  111

List  Of  Figures.

Figure  2.1  :  A  rate-1/3  convolutional  encoder  [52]  .......................................................................  5

Figure  2.2  :  State  diagram  for  encoder  in  Figure  2.1[52]  ..............................................................  6

Figure  2.3  :  Trellis  diagram  for  inputs  of  length  three  to  the  encoder  in  Fig  2.1...........................  7

Figure  2.4  :  The  convolutional  decoding.  ......................................................................................  8

Figure  2.5  :  Hard-decision  Viterbi  decoding  example  [52]  ...........................................................  9

Figure  2.6  :  The  flow  in  general  Viterbi  decoder  [52]  .................................................................  12

Figure  2.7  :  A  branch  metric  computation  block.  ........................................................................  13

Figure  2.8  :  General  butterfly  structure  for  a  (n,1,m)  convolutional  encoder..............................  13

Figure  2.9  :  The  relationships  of  the  states  and  branch  metrics  in  a  butterfly.  ............................  14

Figure  2.10:  ACS  (Add-Compare-Select)  module........................................................................  15

Figure  2.11:  Register  exchange  information  generation  method.  .................................................  16

Figure  2.12:  Two  options  for  forming  registers............................................................................  17

Figure  2.13:  Selective  update  in  traceback  approach....................................................................  17

Figure  2.14:  Clock  gating  scheme  [54].........................................................................................  19

Figure  3.1  :  The  block  diagram  of  a  general  Viterbi  decoder.  .....................................................  22

Figure  3.2  :  A  convolutional  encoder  for  the  proposed  Viterbi  decoder  ....................................  24.

Figure  3.3  :  Block  diagram  of  the  proposed  Viterbi  decoder.......................................................  25

Figure  3.4  :  Butterfly  blocks  ........................................................................................................  26

Figure  3.5  :  Implementation  for  bottom  butterfly.  ......................................................................  27

Figure  3.6  :  The  block  diagram  for  a  wing  of  butterfly.  .............................................................  28

Figure  3.7  :  Proposed  bank  structure  for  the  survivor  path  storage.  ............................................  29

Figure  3.8  :  The  structure  of  the  proposed  survivor  path  storage  module.  ..................................  29

Figure  3.9  :  Relationship  of  states  in  a  butterfly.  .........................................................................  30

Figure  3.10:  Clock  gating  in  the  survivor  path  storage  module....................................................  32

Figure  3.11:  Activation  of  the  trace  back  module.........................................................................  33

Figure  3.12:  A  block  diagram  of  the  trace  back  module...............................................................  33

Figure  3.13:  Multiplexer  approach  for  shifting.............................................................................  35

Figure  3.14:  Gating  circuit  with  overriding  signal........................................................................  36

Figure  3.15:  The  design  flow.  .......................................................................................................  37

Figure  4.1  :  Methodology  for  gate  level  simulation  approach.  [Synopsys  manual]  ....................  40

Figure  4.2  :  Power  dissipation  of  five  different  implementations  of  a  Viterbi  decoder....  47

List  Of  Tables.

Table  4.1:  Area  and  power  dissipation  of  the  three  Viterbi  decoders  ...........................................  42

Table  4.2:  Power  dissipation  of  a  Viterbi  decoder  with  and  without  filtering  the  toggles............  44

Table  4.3:  Power  dissipation  of  a  Viterbi  decoder  with  different  implementations

for  shift  register  module................................................................................................................  45

Table  4.4:  Power  dissipation  of  a  Viterbi  decoder  with  and  without  clock  gating

for  survivor  path  storage  module...................................................................................................  46