 L38: Viterbi Decoder 저전력 설계: Sungkyunkwan Univ. Vada Lab

 L38: Viterbi Decoder 저전력 설계
성균관대학교
전기전자 및 컴퓨터공학부
조준동
1
SungKyunKwan Univ. VADA
Viterbi Decoder
◈ Convolutional Encoder
 K = 3 (Constraint Length)
 R = 1/2 (Rate)
a j= u j+ u j- 1 +u j- 2
+ +
V
U u j a j b j
In f o r m a t io n C o d e w o rd
sequence
A 1 A 0
+
b j= u j+ u j- 2
A ( 3 , 1 / 2 ) C o n v o lu t io n a l e n c o d e r
2
Viterbi Decoder
T im e 0 1 2 3 4 5 6
S ta te
0 0 0 0 0 0
00
1 1 1 1 1 1
10
1 0
1 0
0 1
0 1
1 1
01 0 0 .......
0 1
11
1 0
F ig . 2 . T r e llis d ia g r a m f o r a ( 2 , 1 / 2 ) c o n v o lu t io n a l c o d e
 Information sequence : U = (0,0,1,0,1,0,...)

 Output codeword : V = (00,00,11,10,00,10,
...)
3
Viterbi Decoder
◈ Viterbi Decoder
BM SP
R e c e iv e d
S ig n a l BM U ACSU SM U Decoded
D a ta
PM M
V ite r b i d e c o d e r s tr u c tu r e
4
Viterbi Decoder
 Branch Metric Unit(BMU) : The branch metrics measure the
difference the received symbol and the symbol that causes the transitio
ns
between states in the trellis.
 Add-Compare-Select Unit(ACSU) : To find the survivor path ente

ring each state, the branch metric of a given transition is added to its co
rresponding partial path metric(PM) stored in the path metric memory
(PMM). This new partial path metric is compared with all the other new
partial metric corresponding to all the other transitions entering that sta
te. The transition that has the minimum partial path metric is chosen to
be the survivor path of the state. The path metric of the survivor path of
each state is updated and stored back into the PMM.
 Survivor memory Unit(SMU) : The survivor path are stored in

the SMU. A traceback mechanism is applied on the SMU during the
decoding stage to output the decoded data.
5
Viterbi Decoder
⑴ Low power ACSU VLSI architecture
▶ Conventional ACSU VLSI architecture
S0
sa sa
S0
S 0
sb S1
sb
 Butterfly structure
6
Viterbi Decoder
(s a,S 0)
B M i
Adder
(s a)
PM i- 1 (S 0)
Com p
M i
(s b ,S 0)
B M i Adder
(s a,S 1) Adder
B M i
(S 1)
(sb) Com p
M i
PM i- 1
(s b ,S 1 ) Adder
B M i
 Architecture of conventional ACSU
7
Viterbi Decoder [SKKU. Solution]
―Algorithm
(s a) (s a,S 0 ) (sb) (s b ,S 0)
PM i- 1 + B M i > PM i- 1 + B M i
(s a) (s b) (s b ,S 0 ) (s a,S 0)
PM i- 1 - PM i- 1 > B M i - B M i
☞ The area and power of the lower power ACSU design are reduced by
20% and 30%, respectively, comparing with the conventional ACSU
design
8
▶ Low power ACSU VLSI architecture [C-Y Tsui, ISLPED’99]
9
※ Glitch minimization [Raghunathan, DAC’96]
A 0
A
B 1
B
+
+ 0
C 0
C 1
D 1
D
+
X
X
Y < Y <
(a ) c o m p a re - a d d (b ) a d d - c o m p a re
 (a) Lower power ACSU architecture (b) Conventional ACSU architecture
☞ The power consumption of architecture (a) is larger than that of

architecture (b) by more than 17% because of glitch power dissipatio
n
10
※ Glitches in control logic
A 0
B 1
C
+
C 0 D
D 1
X S
Y < &
F s=0 . F s=1 = A . B
CLK
11
Viterbi Decoder
⑵ Low power traceback VLSI architecture
▶ Systolic Viterbi, traceback decoder[J. Sparso’91]
T ra c e - T ra c e - T ra c e - T ra c e -
ACSU
Back
U n it
B ack
U n it
Back
U n it ..... B ack
U n it
1 2 3 10
T r a c e - B a c k U n it s
T h e s t r u c t u r e o f s y s t o lic V it e r b i d e c o d e r
12
Viterbi Decoder
T im e 0 1 2 3 4 5 6
S ta te
0 0 1 0 2 0 3 1 2 1 3 0
00
2 0 1 0 1 0 3 1 2 1 3 0
10
4 0 2 0 1 0 3 0 2 0
01 .......
p a th m e tr ic
d e c is io n v e c to r
2 0 2 0 2 1 2 1 2 1
11
1 0
S e q u e n c e o f s ta e s o f th e tra c e - b a c k m e th o d e
 Received codeword : V = (00,00,11,10,00,10,

...)
13
Viterbi Decoder
T im e u n it
d e c is io n v e c to r s ta t e w it h s m a lle s t p a t h m e t r ic
0
0
X
1 A C SU
X
0 0
0 0
2 0 X
A C S U
0 X
0 0 0
0 0 0
3 0 0 X
A C S U
0 0 X
1 0 0 0
1 0 0 0
4 0 0 0 X
A C S U
1 0 0 X
14
Viterbi Decoder
.
s u rv iv o r d e p th = 5 K .
.
.
T im e u n it
T 10 T 9 T 8 T 7 T 6 T 5 T 4 T 3 T 2 T 1
1 0 0 1 0 1 1 0 0 0
0 0 1 0 0 1 1 0 0 0
10 A C SU
0 0 0 1 0 0 0 0 0 x
0 0 0 1 0 1 1 0 0 x
11
T T T T T T T T T T T
10 11 10 9 8 7 6 5 4 3 2 1
1 1 0 0 1 0 1 1 0 0 0
1 0 0 1 0 0 1 1 0 0 0
"0 " 11 A C SU
1 0 0 0 1 0 0 0 0 0 x
0 0 0 0 1 0 1 0 0 x
11 1
"1 "
01 10
0 1 1 0 0 1 0 1 1 0 0 0
1 1 0 0 1 0 0 1 1 0 0 0
12 A C SU
0 1 0 0 0 1 0 0 0 0 0 x
0 0 0 0 0 1 0 1 1 0 0 x
10 11 00
15
Viterbi Decoder
.
.
.
0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 0 0 0
19 A C SU 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 x
0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 x
11 00 10 01 01 10 00 10 10 00
1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0
1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 0 0
20 A C SU
1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0
01 10 01 00 10 11 00 01 01 00 0
.
.
.
1 0 0 1 0 1 1 0 0 1 1 0 0 1 0
1 0 0 0 0 0 1 0 1 1 0 0 1 0 0
24 A C SU
1 0 0 1 0 0 0 0 0 1 0 0 0 1 0
1 0 0 1 1 0 1 1 0 0 0 0 0 1 0
01 00 10 11 00 01 1
16
Viterbi Decoder
※ Systolic array decoder 의 문제점
 The systolic array viterbi decoder is organized to input the decision vec
tor and the smallest path metric out of the ACSU and to output the decod
e bit by shifting every register for every cycle.
 This system consumes a great dynamic power consumption due to switch

ing activities of registers which is almost 80% of the total power consum
ption because every data in TBU shifts for every cycle.
17
▶ Our low power trace-back unit
T im e
u n it
0
0
X
X
1 A C S U
C O N T R O L B L O C K
0 0
0 0
X 0
X 0
2 A C S U
C O N T R O L B LO C K
0 0 0
0 0 0
X 0 0
X 0 0
A C S U
3
C O N T R O L B LO C K
18
.
. T ra c e - b a c k
.
T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T 9
0 0 0 1 1 0 1 0 0
0 0 0 1 1 0 0 1 0
X 0 0 0 0 0 1 0 0
X 0 0 1 1 0 1 0 0
9 A C S U
0 0 0 1 1 0 1 0 0 1
0 0 0 1 1 0 0 1 0 0
X 0 0 0 0 0 1 0 0 0
X 0 0 1 1 0 1 0 0 0
1 0 A C S U 1
1
0 0 0 1 1 0 1 0 0 1 1
0 0 0 1 1 0 0 1 0 0 1
X 0 0 0 0 0 1 0 0 0 1
X 0 0 1 1 0 1 0 0 0 0
1 1 A C S U 1 0
0 1
19
.
.
.
.
0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0
0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0
X 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0
X 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0
1 9 A C S U 0 1 1 0 1 0 0 1 0 1
0 0 0 0 0 1 1 0 0 1
0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1
0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1
0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0 1
2 0 A C S U 0 0 0 0 1 1 0 0 1 0
0 0 1 1 0 1 0 0 1 0 1
0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1
0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1
0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0 1
2 1 A C S U 1 1 0 1 0 0 1 0 1
0 0 0 0 0 1 0 1
1 0
20
 After decision vector and the smallest path metric generated from ACSU
are transferred to the Control Block (CB), the CB outputs the decision ve
ctor and the smallest path metric with the right cycle using a counter and
a multiplexer.
 The register array, which stores the value of trace-back from the CB, was
provided to finally output decoded bit, not by shifting all higher 4-bit d
ecision vector as in the classical TBU, but by shifting the lower 2-bit
only, which is the smallest path metric, to the left
21
◈ Experimental Result (area 11% , power 40% )
Power Dissipation
Area
8000 1600
7000 1400
6000 1200
pow er(uW )
5000 1000
gates
4000 800
3000 600
2000 400
1000 200
0 0
2 3 4
2 3 4
K
K
Trace-back Unit Low Power Trace-back Unit Trace-back Unit Low Power Trace-back Unit
22
Viterbi Decoder [Stanford Solution]
⑶ Low Power Asynchronous Viterbi Decoder [Y.h.Lee , Stanford]
▶ Algorithm
c o n v e r g e p o in t
t im e
t im e n
n+1
T r a c e b a c k p r o c e s s in g
23
① 초기화 : 구속장의 5 배의 trellis 를 traceback 하고 , 그 경로를
저장한다 .
② Loop
A. 추적과 비교 : 임의의 초기 스테이트를 선택해 trace back 을 시작
한다 . 동시에 , route 를 추적해 나가면서 각 nod
e 에서
저장된 route 와 비교한다 .
B. 비교 값이 같으면 추적을 멈추고 저장된 route 를 버린다 . 같지 않
을 때는 A 과정을 반복한다 .
③ 각각의 입력 신호에 대해 ② 과정을 반복한다 .
24
▶ Implementation
S e lf-p r e c h a r g e &
S e lf-r e q u e s tin g
if n o t fo u n d
P r e v io u s p a th
In p u t P o r t
A d d re s s T ra c e B a c k
S u r v iv in g R D /W R C o n tr o l U n it O s c illa to r
P a th R in g
M e m o ry M C o m p a r is o n
U S h ift R e is te r L o g ic
X R equest
R equest fo rm
if P a th is n o t A C S
fo u n d
M e m o ry M a n a g e m e n t
A d d r e s s R D /W R U n it
A c k n o w le d g e to
C o n tro l
A C S
if p a th is fo u n d
 Self-timed TBU block diagram
25
Viterbi Decoder
① Self-timed TBU 가 request 신호를 기다리는 동안 전력 소모가 없다 .
② ACS 는 스테이트 결정 데이터를 버리기 위해 request 신호를 내보낸
다.
③ TBU 는 이전의 surviving path memory 와 previous path memory 를 읽어 들여 비
교한다 .
④ 같지 않으면 , TBU 는 previous path memory 를 update 하고 self-

precharging, self-requesting 을 한 다음 ③ 과정을 반복한다 . 같으면 ,
⑤ 과정으로 간다 .
⑤ TBU 는 ACS 에 scknowledgement 신호를 보내고 , 다음 ACS 의 reques
t
신호를 위해 self-precharge 한다 .
26
Low-Power Bit-Serial Viterbi Decoder
H. Suzuki, Y. N. Chang, K. K. Parhi “Low-Power Bit-Serial Viterbi Decoder for 3rd Generation W-CDMA Sys
tem”, 1999, CICC
◈ Abstract
 This paper presents a low-power bit-serial Viterbi decoder chip

with the coding rate =1/3 and the constraint length K=9(256
states)
 The Add-Compare-Select(ACS) units have been designed using

bit-serial arithmetic and a power efficient trace-back scheme and
an application-specific memory have been developed for the trace-
back operation.
 The chip was implemented using 0.5m CMOS technology and is

operative at 20Mbps under 3.3V and 2Mbps under 1.8V. The
power dissipation is only 9.8mW at 2Mbps operation under 1.8V
27
◈ Architecture Overview
 256 bit-serial ACS units are placed in parallel and each ACS unit i
nclude state metrics storage
 Trace-back block, a 256 x 48 bit memory is required for the surviv

or path length of 48
28
 Bit-Serial Viterbi Decoder Chip Diagram
29
◈ Bit-Serial ACS Unit
 Bit-serial ACS unit
30
 Each ACS unit has three full-adders.
 Two of them are used to add the state metric and the branch metric
and the third one is used to compare two new state metrics
 Reducing the overhead down to 17% of the whole area of the ACS
unit
31
◈ Trace Back Strategy
 Trace Back operation

32
 The memory size required in this paper is twice as large as the min
imum memory size(256 x 2).
 After 48 “TRACE BACK” operations, 24 decoded bits are obtaine

d consecutively.
 Two separate pointers, namely, a read pointer and a write pointer a

re required and the speed of the read pointer should be three times
as fast as that of the write pointer
 This operation was implemented with single-port memories using

a time-multiplexed access method.
33

 L38: Viterbi Decoder 저전력 설계: Sungkyunkwan Univ. Vada Lab

Uploaded by

Copyright:

Available Formats

 L38: Viterbi Decoder 저전력 설계: Sungkyunkwan Univ. Vada Lab

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

 L38: Viterbi Decoder 저전력 설계: Sungkyunkwan Univ. Vada Lab

Uploaded by

Copyright:

Available Formats

 L38: Viterbi Decoder 저전력 설계

 Information sequence : U = (0,0,1,0,1,0,...)

 Add-Compare-Select Unit(ACSU) : To find the survivor path ente

 Survivor memory Unit(SMU) : The survivor path are stored in

☞ The power consumption of architecture (a) is larger than that of

 Received codeword : V = (00,00,11,10,00,10,

 This system consumes a great dynamic power consumption due to switch

③ 각각의 입력 신호에 대해 ② 과정을 반복한다 .

④ 같지 않으면 , TBU 는 previous path memory 를 update 하고 self-

 This paper presents a low-power bit-serial Viterbi decoder chip

 The Add-Compare-Select(ACS) units have been designed using

 The chip was implemented using 0.5m CMOS technology and is

 Trace-back block, a 256 x 48 bit memory is required for the surviv

 Bit-Serial Viterbi Decoder Chip Diagram

 Bit-serial ACS unit

 Each ACS unit has three full-adders.

 Trace Back operation

 After 48 “TRACE BACK” operations, 24 decoded bits are obtaine

 Two separate pointers, namely, a read pointer and a write pointer a

 This operation was implemented with single-port memories using

You might also like