오류정정부호 Viterbi decoder의 이해 및 Convolutional encoder 설계 고속 디지털 시스템 설계 한양대학교

목차 Convolutional Codes Representation of Convolutional Codes Trellis Diagram Viterbi Decoder Viterbi Decoder의 구조 Viterbi Decoder – Example Convolutional Encoder 설계

Convolutional Codes(1/7) 오류정정부호의 분류 1. Tree code Linear tree code Linear recurrent codes Convolutional codes 2. Block code 선형부호(Linear codes) 순환부호(Cyclic code)

Convolutional codes(2/7) 1955년 Elias의해 소개. Random error에 강한 특성. AWGN( Addtive White Gaussian Noise) 채널에서의 오류정정능력 우수. 인터리버(Interleaver/Deinterleaver)를 이용하여 Burst error에 대해서도 적용가능. 쉽게 Soft decision coding이 가능하다. 약 2 dB 추가적인 coding gain을 얻을 수 있다. Easy multirate codec Implementation. Convolutional codes의 응용 Satellite communications VSAT, INMARSAT, HDTV, MSAT,… Mobile communication, GSM, IMT-2000… Used for most radio communication systems

Convolutional codes(3/7) 일반적인 통신 시스템의 구성

Convolutional codes(4/7) ( n, k, m) Convolutional encoder m : 메모리 소자의 개수 ( shift registers ) k : 입력 비트 수 n : 출력 비트 수 K : 구속장(constraint length) 한 개의 입력 비트가 영향을 끼치는 output sequence의 길이 K = m +1 Code rate : k/n Example : (2,1,3) convolutional code k =1, n = 2, shift registers = 3, code rate = 1/2 , K = 4

Convolutional codes(5/7) ( 2, 1, 3) Convolutional encoder (a) Recursion formula

Convolutional codes(6/7) Generator sequences (impulse response) Recursion formula using generator sequences Information sequence : Generator sequence :

Convolutional codes(7/7) Output sequence:

Representation of Convolutional Codes(1/9) Generation polynomials g(1)(D) = 1 + D2 + D3 g(2)(D) = 1 + D + D2 + D3 Gernerator matrix

Representation of Convolutional Codes(2/9) Impulse response encoder Register contents Branch Word V1 V2 1000 1 0100 0010 0001 Input u Branch Word 1 11 01 11 11 00 00 00 00 11 01 11 11 Module 11 01 00 01 10 00 11 Input seq : 1000 Output seq : 11, 01, 11, 11

Representation of Convolutional Codes(3/9) Connection pictorial

Representation of Convolutional Codes(4/9) Connection pictorial Input sequence : 1011 Output sequence : 11 01 00 01 10 00 11 Input sequence가 각 시간(t)에 대하여 하나씩 입력 입력된 Input bit를 flush 하기 위하여 K-1개의 0을 넣어준다. Output sequence는 impulse sequence의 선형 중첩이 된다.

Representation of Convolutional Codes(5/9) State representation of encoder K의 값이 커짐에 따라 상태의 수는 2K-1로 증가하게 된다. 큰 구속장을 가진 convolutional code에서는 표현이 어렵다. 시간의 변화에 대한 개념이 나타나지 않음

Representation of Convolutional Codes(6/9) Tree representation of encoder 시간에 대한 개념 포함. 구속장이 길어질수록 대역폭이 지수적으로 증가하여 상태의 표현이 힘들다. 가지의 오른쪽은 Input: 0을 나타내며 왼쪽 가지는 Input: 1을 나타낸다. branch의 수가 2L 의 함수로 증가한다.( L input bit수 )

Representation of Convolutional Codes(7/9) Tree representation of encoder Example Input sequence : 0, 1, 1, 0, … Output sequence : 00, 11, 10, 10, …

Representation of Convolutional Codes(8/9) Trellis Diagram 대역폭의 증가없이 부호의 tree를 간단하게 표현 각 시간 단위에서 trellis는 2K-1 의 possible encoder state들을 나타내기 위하여 2K-1의 node 존재 Trellis Depth가 구속장 K만큼 진행후 고정된 주기적 구조 형성. Trellis diagram은 계속해서 반복적인 구조 사용 가능.

Representation of Convolutional Codes(9/9) Trellis diagram : butterfly structure 각각의 state는 butterfly 구조를 가지고 있다.

Trellis Diagram(1/4) Example Generation polynomial G = ( 15, 17 ) Code rate R = ½ Constraint length K = 4 Input sequence

Trellis Diagram(2/4)

Trellis Diagram(3/4) 실선은 입력 bit가 0을 나타내며 점선은 입력 bit 1을 나타낸다

Trellis Diagram(4/4) Input sequence : 0, 1, 1, 0, 0, 1 … Output sequence : 00, 11, 10, 10, 00, 00, …

Catastrophic Code(1/2) # of decoding error bits -> => Catastrophic code ( undesirable code )

Catastrophic Code(1/2) Generator가 최소 1차의common polynomial factor를 가지면 catastrophic error 발생 noncatastrophic code의 조건 For ( n, 1, m ) code Generator polynomials Example: gcd (1 + D, 1 + D2 ) = 1 + D => Catastrophic code

Optimal Convolutional Code R= 1/2 Generator polynomials D free m G1 G2 G3 2 5 7 8 3 13 17 6 15 10 4 23 35 25 33 37 12 65 57 47 53 75 133 171 145 175 345 237 225 331 367 16 753 561 557 663 711 18 9 1167 1545 1117 1365 1633 20

Free Distance(1/3) Convolution encoder에서의 모든 0의 입력에 대한 출력 data path는 모두 all zero path이여야 한다. 만약 error의 발생경우 all zero path는 존재하지 않는다. Error이 최소일때의 path는 0이상의 hamming distance를 가지게 되는데 이때의 최소가 되는 거리를 최소 자유거리 또는 유클리디안 자유거리라 하며 dfree라 한다. 유클리디안 자유거리는 에러정정능력과 다음의 관계에 있다.

Free Distance(2/3) 유클리디안 자유거리를 구하기 위한 가정 유클리디안 자유거리의 측정 All-zero 열이 입력될때 시작과 끝의 상태가 0이고 그 사이의 상태는 0가 아니여야 한다. 유클리디안 자유거리의 측정 00 상태로 시작해서 다시 00 state로 돌아오는 path중 hamming distance를 구하여 최소가 되는 hamming distance를 구한다. 1) trellis diagram을 그린다. 2) 00 state로 시작해서 00 state로 되돌아오는 path를 모두 찾는다. 3) 2)에서 찾아진 모든 path들 간에 hamming distance를 계산하여 trellis diagram에 출력 부호열 대신 표기한다. 4) 각 path의 hamming distance의 합을 구한다. 5) hamming distance의 합이 최소인 path를 찾는다. 이 path의 hamming distance가 유클리디안 자유거리 dfree이다.

Free Distance(3/3) Example Information sequence : 0110000… Output sequence : 00 11 10 10 00 11 00…. Dfree = 2 + 1 + 1 + 0 + 2 = 6

Hard decision / Soft decision Q = 2 : Hard decision Q > 2 : Soft decision 이상적인 soft decision의 값은 무한대이다. 위에 그림은 Q = 8인 soft decision을 나타낸다.

Representation of soft decision data Offset-binary representation Sign-magnitude representation signal Hard decision data Offset-binary representation Sign-magnitude representation Most negative Least negative 1 000 111 001 110 010 101 011 100 Least positive Most positive

Application of Convolution Codes(1/2) Constraint length K = 5 (m = 4) (a) Generator polynomials : ( 23, 35 ) (b) dfree = 7 GSM system Constraint length K = 6 (m = 5) (a) Generator polynomials : ( 65, 57 ) (b) dfree = 8 (c) IS-54 american digital cellular system Constraint length K = 7 (m = 6) (a) Generator polynomials : ( 133, 171 ) (b) dfree = 10 Most satellite communication system

Application of Convolution Codes(1/2) Constraint length K = 9 (m = 8) (a) Generator polynomials : ( 753, 561 ) (b) dfree = 12 IS-95 CDMA system( forward channel ) (a) Generator polynomials : ( 557, 663, 711 ) (b) dfree = 18 IS-95 CDMA system( reverse channel )

Viterbi Decoder(1/2) Convolutional codes의 복호화 방법 Sequential decoding Code tree 에 서 정확한 경로를 찾아가는 시행 착오적인 방법 탐색상태의 수는 constraint length 와 무관 Sequential decoding, Fano algorithm, stack algorithm 탐색 되는 state metric수가 random 변수 잘못된 가정과 역방 탐색의 예상 수 채널 SNR 함수 계산량의 다양성을 때문에 도착되는 sequence 들을 저장하기 위해 buffer사용 Threshold decoding 낮은 부호 이득 가장 간단한 decoding hardware

Viterbi Decoder(2/2) Viterbi decoder 높은 부호 이득 높은 하드웨어의 복잡도 하드웨어 복잡도는 state의 수 ( 2K-1 ))에 비례한다. Error 확률은 constraint length에 지수적으로 감소 최대 우호 복호( Maximum Likelihood decoding ) 사용 최근 convolutional decoder로 가장 많이 사용. Soft decision decoding 사용 시 hard decision에 비하여 약 2dB의 추가적인 부호이득을 얻을 수 있다. => 약간의 복잡도 증가

Viterbi Decoder의 구조(1/7) Branch Metric Calculation(BMC) Path Metric Calculation Path Metric Memory Add-Compare-Select (ACS) Trace Back Memory Normalization

Viterbi Decoder의 구조(2/7) Branch Metric Calculation( BMC ) State의 수 : 2m Encoder 의 입력이 1이면 lower branch Encoder 의 입력이 0이면 upper branch Hard Decision Received sequence와 각각의 branch간의 codeword와의 hamming distance를 구하여 branch metric 값을 계산한다. Soft Decision 신호로 받은 soft decision data는 BMC로 입력 된다. 3bit soft decision의 경우 다음과 같이 표현된다. J1 = x1 x2 x3 J2 = y2 y1 y0 Branch Metric Value BM0(t) BM1(t) BM2(t) BM3(t) Encoded (vi(1) , vi(2) ) 00 01 10 11

Viterbi Decoder의 구조(3/7) 4개의 branch metric 값은 J1, J2값을 이용하여 다음과 같이 계산할 수 있다. 00 => BM0(t) = (2x – 1 – J2) + (2x –1 – J1) 01 => BM1(t) = (2x – 1 – J2) + J1 10 => BM2(t) = J2 + (2x –1 – J1) 11 => BM3(t) = J1 + J1 BM3(t) = 2x+1 – 2 - BM0(t), BM2(t) = 2x+1 – 2 - BM1(t) Example

Viterbi Decoder의 구조(4/7) ACS ( Add Compare Select ) 와 Path Metric Memory BMC(Branch Metric Calculate)에서 계산된 branch metric값과 현재상태의 Path metric 값을 이용하여 새로운 path metric 값을 계산한다. Path Metric의 개수 = state의 개수 = 2K-1 = 2m ( K : 구속장 ) K가 4인 convolutional encoder의 path metric 값은 다음과 같다. Path metric 개수 = 24-1 = 8 PM0(t), PM1(t), PM2(t), PM3(t), PM4(t), PM5(t), PM6(t), PM7(t)

Viterbi Decoder의 구조(5/7) PMi3(t) = Min{ PMi1(t-1) + BM1(t), PMi2(t-1) + BM2(t) } PMi4(t) = Min{ PMi1(t-1) + BM2(t), PMi2(t-1) + BM1(t) } PMi3(t) = Min{ PMi1(t-1) + BM0(t), PMi2(t-1) + BM3(t) } PMi4(t) = Min{ PMi1(t-1) + BM3(t), PMi2(t-1) + BM0(t) } 여기서 (i1, i2) , (j1, j2) => ( 2P, 2P+1 ) (i3, i4) , (j3, j4) => ( P, P+4 ) 단 ( K = 4 )

Viterbi Decoder의 구조(6/7) Normalization 현재 ACS의 출력으로 나온 Path metric값은 계속해서 Branch metric이 더해지므로 값이 증가하게 된다. 따라서 하드웨어적으로 Path Metric Memory의 크기의 증가를 가져오게 된다. 이를 방지하기 위하여 현재 상태의 전체 Path Metric값중 가장 작은 값을 찾아서 각각의 현재 상태의 Path Metric 값을 가장 작은 값으로 빼 줌으로서 가장 작은 metric 값이 0이 되게 한다.

Viterbi Decoder의 구조(7/7) TraceBack memory Trellis diagram에서 survivor path를 저장하고 Traceback 에 의하여 복호화된 비트를 찾아내는 역할을 하는 부분. Trellis diagram에서 현재 state값 중 가장 작은 값을 갖는 state를 초기값으로 하여 Traceback algorithm을 적용하여 원래 입력 정보와 확률이 가장 높은 값을 선택. ACS에서 이전 node 2p 가 생존하면 pointer 0을 저장, 2p + 1이 생존하면 pointer에 1을 저장한다. Traceback depth가 크면 BER의 성능이 좋아진다. 이상적인 traceback depth는 무한대 이지만 하드웨어 구현상 5~6배의 traceback depth 사용한다.

Viterbi Decoder - Example(1/16) Generation polynomial G = ( 15, 17 ) Code rate R = ½ Constraint length K = 4 Input sequence ( 011000 )

Viterbi Decoder - Example(2/16)

Viterbi Decoder - Example(3/16) 각각의 branch에 branch metric을 구하고 각각의 node마다 path metric을 구한다 Branch metric : 수신된 값과 각 branch에서의 천이 값과의 hamming distance를 구한다. Path metric : 전 단의 path metric + 각 branch에서의 branch metric을 구한다.

Viterbi Decoder - Example(4/16) t0-t1의 branch metric, path metric Received seq : 00 branch : S0-S0 : 00 => branch metric : 0 S0-S4 : 11 => branch metric : 2 Path metric : S0 : 0 + 0 = 0 S4 : 0 + 2 = 2 t1-t2의 branch metric, path metric Received seq : 11 S0-S0 : 00 => branch metric : 0

Viterbi Decoder - Example(5/16) Received sequence를 이용하여 branch를 구한다. T3에서의 path metric 값과 t3과 t4사이의 branch metric값을 더하여 t4에서의 path metric 값을 구한다. 각 stage마다 가장 작은 state를 찾아

Viterbi Decoder - Example(6/16) State(t=3) Branch BM PM+BM Survivor path State(t=4) S0 4 S0-S0 2 6 1 3 S0-S4 S1-S0 S1 S2-S1 S1-S4 5 S3-S1 S2 S4-S2 S2-S5 S5-S2 S3 S6-S3 S3-S5 S7-S3 S4 S4-S6 S5 S5-S6 S6 S6-S7 S7 S6-S1 S7-S7

Viterbi Decoder - Example(7/16)

Viterbi Decoder - Example(8/16) State(t=4) Branch BM PM+BM Survivor path State(t=5) S0 3 S0-S0 1 4 2 S0-S4 S1-S0 S1 S2-S1 S1-S4 S3-S1 S2 S4-S2 S2-S5 S5-S2 5 S3 S6-S3 S3-S5 S7-S3 S4 S4-S6 6 S5 S5-S6 S6 S6-S7 S7 S6-S1 S7-S7

Viterbi Decoder - Example(9/16)

Viterbi Decoder - Example(10/16) State(t=5) Branch BM PM+BM Survivor path State(t=6) S0 2 S0-S0 S0-S4 4 S1-S0 5 S1 3 S2-S1 6 1 S1-S4 S3-S1 S2 S4-S2 S2-S5 S5-S2 S3 S6-S3 S3-S5 S7-S3 S4 S4-S6 S5 S5-S6 S6 S6-S7 S7 S6-S1 S7-S7

Viterbi Decoder - Example(11/16)

Viterbi Decoder - Example(12/16) State(t=6) Branch BM PM+BM Survivor path State(t=7) S0 2 S0-S0 4 1 S0-S4 S1-S0 S1 S2-S1 3 S1-S4 S3-S1 6 S2 S4-S2 S2-S5 5 S5-S2 S3 S6-S3 S3-S5 S7-S3 S4 S4-S6 S5 S5-S6 S6 S6-S7 S7 S6-S1 S7-S7

Viterbi Decoder - Example(13/16)

Viterbi Decoder - Example(14/16) State(t=7) Branch BM PM+BM Survivor path State(t=8) S0 2 S0-S0 S0-S4 4 S1-S0 5 S1 3 S2-S1 6 1 S1-S4 S3-S1 S2 S4-S2 S2-S5 S5-S2 S3 S6-S3 S3-S5 S7-S3 S4 S4-S6 S5 S5-S6 S6 S6-S7 S7 S6-S1 S7-S7

Viterbi Decoder - Example(15/16) 위의 그림에서 최종 stage에서 가장 작은 값을 찾아 초기state로 정하고 traceback 과정을 진행한다. 위의 그림에서 최종 stage에서의 가장 작은 metric값은 2이며 이때의 값에 대하여 Traceback 하여 복호 과정을 수행한다.

Viterbi Decoder - Example(16/16) Input sequence Decoding data Traceback memory안에 저장되어있는 값을 이용하여 최종 decoding data를 구할 수 있다. 0 1 1 1 0 0 0 0 00 11 10 11 01 00 11 00 t8 t7 t6 t5 t4 t3 t2 t1 t0 1 S7 S5 S3 S1 S6 S4 S2 S0 Lowest state

Convolutional Encoder 설계 Example Generation polynomial G = ( 15, 17 ) Code rate R = ½ Constraint length K = 4 Input sequence ( 011000 )

Convolutional Encoder 설계 - parameter /******************************************************************************************/ // MODULE : Parameter // // FILE NAME: parameter.v // VERSION: 1.0 // DATE: FAB 2, 2004 // AUTHOR: DONG KI CHOI // Description: This file defines a parameter. // defines simulation period `define FULL 20 `define HALF 10 `define PERIOD `FULL // defines delay `define DEL 1 // define parmeter `define CONS_K 4 `define DATA_WIDTH 4 `define BUS_WIDTH 16

Convolutional Encoder 설계 – D-F.F(1/2) /******************************************************************************************/ // MODULE : D-type flip flop // // FILE NAME: dff_n.v // VERSION: 1.0 // DATE: JAN 14, 2004 // AUTHOR: DONG KI CHOI // Description: This module defines a D-type flip flop. // reset is active-low `include "parameter.v" module dff_n( clk, rst_n, d, q ); // parameter parameter CARDINALITY = 1;

Convolutional Encoder 설계 – D-F.F(2/2) // input data input clk; input rst_n; input [CARDINALITY-1:0] d; // output data output [CARDINALITY-1:0] q; reg [CARDINALITY-1:0] q; wire [CARDINALITY-1:0] d; // main code always @(posedge clk or negedge rst_n) begin if ( ~rst_n ) q <= 0; else q <= d; end endmodule

Convolutional Encoder 설계 – Convolutional encoder(1/2) /******************************************************************************************/ // MODULE : Convolution encoder // // FILE NAME: convol.v // VERSION: 1.0 // DATE: JAN 14, 2004 // AUTHOR: DONG KI CHOI // CODE TYPE: RTL Level // Description: This module defines a Convolution encoder. // K = 4, generation polynomial = (13,17), bit rate = 1/2 `include "parameter.v" module convol( clk, rst_n, data_in, data_out ); // input data input clk; input rst_n; input data_in;

Convolutional Encoder 설계 – Convolutional encoder(2/2) // output data output [1:0] data_out; wire [`CONS_K-1:0] poly_a; // poly a = 13 wire [`CONS_K-1:0] poly_b; // poly b = 17 wire [`CONS_K-1:0] wa; wire [`CONS_K-1:0] wb; wire [0:`CONS_K-1] sh_reg; // main code assign poly_a = 4'b1011; assign poly_b = 4'b1111; dff_n df0( clk , rst_n, data_in, sh_reg[0] ); dff_n df1( clk , rst_n, sh_reg[0], sh_reg[1] ); dff_n df2( clk , rst_n, sh_reg[1], sh_reg[2] ); dff_n df3( clk , rst_n, sh_reg[2], sh_reg[3] ); assign wa = poly_a & sh_reg[0:`CONS_K-1]; assign wb = poly_b & sh_reg[0:`CONS_K-1]; assign data_out[0] = wa[3]^wa[2]^wa[1]^wa[0]; assign data_out[1] = wb[3]^wb[2]^wb[1]^wb[0]; endmodule

Convolutional Encoder 설계 – testbench(1/2) /******************************************************************************************/ // MODULE : test bench-convolution encoder // // FILE NAME: test_conv.v // VERSION: 1.0 // DATE: JAN 14, 2004 // AUTHOR: DONG KI CHOI // CODE TYPE: Behavioral Level // Description: This module defines a test bench convolution encoder. `include "parameter.v" module test_conv(); reg rst_n; reg data_in; reg clk; wire [1:0] data_out; // main code convol conv ( .clk(clk), .rst_n(rst_n), .data_in(data_in), .data_out(data_out) ); always #(`PERIOD/2) clk <= ~clk; initial begin

Convolutional Encoder 설계 – testbench(2/2) clk <= 0; rst_n <= 1; #10; rst_n <= 0; #10; rst_n <= 1; data_in <= 0; #`PERIOD; data_in <= 1; #`PERIOD; $stop; end endmodule

참고문헌 [1] 이문호, 김순영,“오류 정정 이론: 터보코드의 원리와 응용”, 도서출판 영일, 2001.3 [2] 이문호,” 갈루이스필드,리드솔로몬,비터비,터보부호기설계”, 도서출판 영일, 2003.1 [3] Rorabaugh, C.Britton,”Error Coding Cookbook:practical C/C++ routines and recipes for error detection and correction”,McGraw Hill.1995