CDMA 이동통신시스템과 부호이론

오류 정정 부호화 기법 오류 정정 부호화 기법 채널 상에서 발생하는 오류를 효율적으로 정정하기 위하여 사용되는 방식으로써 같은 전송 에너지를 사용하고서도 부호화 방식을 사용하지 않은 시스템에 비하여 더 우수한 성능을 얻을 수 있다. 소스 부호기에서 나오는 정보 비트에 임의의 부가 비트 (redundancy)를 덧붙여 오류가 발생하는 채널로 전송하기 위한 부호어를 만들고(부호화), 수신단에서는 수신된 부호어로부터 송신단에서 덧붙인 부가의 비트를 이용하여 오류가 없는 원래의 정보 비트를 복원(복호화)하게 된다. 1

오류 정정 부호화 방식 오류 정정 부호화 방식 블록 부호화(block coding)방식 : 정보비트에 어떤 대수적인 연산을 적용하여 부가비트를 첨가하는 방식(복호시에도 부호화 작업의 역연산에 의하여 원래의 정보 복원) 예 : BCH 부호, Reed Solomon 부호 트리 부호화(tree 또는 trellis coding) 방식 : 대수적인 연산과는 상관없이 각 부호 나름대로의 topology에 의해 부/복호를 수행한다. 예 : convolutional 부호 1

채널 부호의 특성 및 장단점(1) Convolutional codes ( Viterbi Algorithm ) 구속장 k의 증가에 따른 복잡도의 증가. 긴 지연으로 인한 저속 전송(수십 Kbps – 수십 Mbps) 연집에러(burst error)에 약함(AWGN 채널에서 이상적) 격자도 진행의 한계. 10-7이상의 에러율에서 좋은 성능 이동 통신에서 주로 사용

채널 부호의 특성 및 장단점(2) Block codes ( Reed-Solomon Algorithm ) 에러 정정 능력에 따른 복잡도의 선형적 증가 또는 지수적 증가 정정 능력 t 이상의 에러는 수정 불가 고속 전송 가능 (수백 Mbps) 연집에러(burst error)에 강함(페이딩 채널에서 좋은 성능) Erasure 의 검출 및 정정 10-7이하의 에러율에서 좋은 성능 CD, DAT(Digital Audio Tape), ATM 망에서 사용

채널 부호의 특성 및 장단점(3) Concatenated codes ( Viterbi / Reed-Solomon Algorithm ) 짧은 구속길이와 낮은 에러정정능력 t로 좋은 성능 긴 지연으로 인한 저속 전송(수십 Kbps – 수십 Mbps) 랜덤, 연집에러에 모두 강함 구현이 어려움 (인터페이스와 전력 문제 등) 위성 통신에 사용 Turbo codes 재귀적(recursive) 구조의 연산 가능(매우 높은 연산량) 재귀를 통한 반복이 많아질수록 좋은 성능(반면, 긴 지연으로 인한 저속 동작) 복호기의 복잡성이 매우 높음 (인터리버와 디인터리버 포함)

오차 정정 방식 종류 Block Codes Convolutional Codes Concatenated Codes - CRC (for error detection only) - Hamming - BCH , RS etc … Convolutional Codes - Sequential decoding - Viterbi decoding Concatenated Codes - Serially concatenated - Parallel concatenated(Turbo)

(n,k) Linear Block Coding k information bits (n,k) block encoder n channel symbols channel error (n,k) block decoder k output bits erasures

GF(2) Operations Mod-2 addition (XOR gate) Mod-2 multiplication + 1 1 Mod-2 addition (XOR gate) Mod-2 multiplication (AND gate) (NOTE) 1+1=0  1=-1

Systematic Block Code (n,k) linear block code k information bits (n-k) parity bits n bits - 비체계적 부호는 체계적 부호에 비해 특별히 장점이 없음 - 오류가 발생하지 않은 경우 복호 절차가 필요 없음

Hamming Distance 비트 대 비트로 비교해 보았을 때 서로 다른 비트 자리의 갯 수   d(c1,c2) = 2 - dmin ; minimum distance

Error Correcting /Detecting Capability Error Correcting Capability, t 단, x 는 x 보다 크지 않은 정수 t  Error Detecting Capability dmin –1 발생오류가 dmin 과 같거나 커도 대부분 검출됨 오류로 인해 다른 부호어로 변경되는 경우 오류가 검출되지 않으며 이러한 형태의 오류를 검출불가오류(undetected error pattern)라 함

Hamming Code Parameters (m>2) code length n = 2m -1 parity bits n-k = m information bits k = 2m -1-m minimum distance dmin = 3 - Example : m=3, n=8-1=7, n-k=3, t=1  (7,4) Hamming code - Example : m=7, n=128-1, n-k=7, t=1  (127,120) Hamming code

Hamming Code Examples For m>2, m (n,k) m (n,k) 3 (7,4) 7 (127,120) 3 (7,4) 7 (127,120) 4 (15,11) 8 (255,247) 5 (31,26) 9 (511,502) 6 (63,57) …

Generator and Parity Check Matrix Generator Matrix, G G = Parity Check Matrix, H H = (NOTE) G is the null space of H , GHT=0 : k x n matrix : (n-k) x n matrix

Encoding of Hamming Codes (n,k) Hamming Code message u = (u0 u1 u2 . . . uk-1) message c = (c0 c1 c2 . . . cn-1)  c = uG = (u0 u1 u2 . . . uk-1) u1 u0 uk-1 ㆍ ㆍ ㆍ ㆍ ㆍ CL k to n encoder c0 c1 c2 cn-1

Example (15,11) Hamming Code ㆍ ㆍ ㆍ ㆍ ㆍ CL k to n encoder message u = (u0 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10)  c = uG = (u0 u1 u2 . . . u10) u1 u0 uk-1 ㆍ ㆍ ㆍ ㆍ ㆍ CL k to n encoder c0 c1 c2 cn-1

Example (15,11) Hamming Code message u = (u0 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10) message c = (c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 c11 c12 c13 c14 )  c = uG = (u0 u1 u2 . . . u10) c0 = u0, c1 = u1, . . . c10 = u10 c11 = p11 = u4 + u5+ . . . +u10 c12 = p12 = u1 + u2 + u3 +u7 + u8 + u9 + u10 c13 = p13 = u0 + u2 + u3 +u5 + u6 + u9 + u10 c14 = p14 = u0 + u1 + u3 +u4 + u6 + u8 + u10

Example (15,11) Hamming Encoder

Decoding of Hamming Code Standard Array Decoding - not good for large codes Syndrome Decoding - Table look-up decoding - widely used for Hamming decoding c e r S = rHT =(c+e) HT =c HT +e HT = e HT

Syndrome Decoding Structure rn-1 ㆍ ㆍ ㆍ ㆍ ㆍ CL syndrome generator s0 s1 s2 sn-k (n-k) to n table look-up decoder c0 c1 c2 cn-1

Example (7,4) Hamming Decoder

Modification of Hamming Codes Why modification? : a limited range of values of length n and dimension k ; the available values may not suit the system Expanding(Extending) Shortening Expurgating (CRC)

Expanding of Hamming Codes Expanding(Extending) : adding extra parity check bit (overall check bits) : increasing n while keeping k the same Example : (7,4) Hamming (8,4) expanded Hamming message (7,4) (8,4)  (0 0 0 0) (1 0 0 0) (0 1 0 0) (1 1 0 0) (0 0 1 0) (1 0 1 0) (0 1 1 0) (1 1 1 0) (0 0 0 1) (1 0 0 1) (0 1 0 1) (1 1 0 1) (0 0 1 1) (1 0 1 1) (0 1 1 1) (1 1 1 1) (0 0 0 0 0 0 0) (1 1 0 1 0 0 0) (0 1 1 0 1 0 0) (1 0 1 1 1 0 0) (1 1 1 0 0 1 0) (0 0 1 1 0 1 0) (1 0 0 0 1 1 0) (0 1 0 1 1 1 0) (1 0 1 0 0 0 1) (0 1 1 1 0 0 1) (1 1 0 0 1 0 1) (0 0 0 1 1 0 1) (0 1 0 0 0 1 1) (1 0 0 1 0 1 1) (0 0 1 0 1 1 1) (1 1 1 1 1 1 1) (0 0 0 0 0 0 0 0) (1 1 0 1 0 0 0 1) (0 1 1 0 1 0 0 1) (1 0 1 1 1 0 0 0) (1 1 1 0 0 1 0 0) (0 0 1 1 0 1 0 1) (1 0 0 0 1 1 0 1) (0 1 0 1 1 1 0 0) (1 0 1 0 0 0 1 1) (0 1 1 1 0 0 1 0) (1 1 0 0 1 0 1 0) (0 0 0 1 1 0 1 1) (0 1 0 0 0 1 1 1) (1 0 0 1 0 1 1 0) (0 0 1 0 1 1 1 0) (1 1 1 1 1 1 1 1) (NOTE) Expanding code increase in dmin when dmin has an odd value

Shortening of Hamming Codes : reducing the information bits, keeping the number of parity bits the same Example : (7,4) Hamming (6,3) shortened Hamming message (7,4) (6,3) (0 0 0 0) (1 0 0 0) (0 1 0 0) (1 1 0 0) (0 0 1 0) (1 0 1 0) (0 1 1 0) (1 1 1 0) (0 0 0 1) (1 0 0 1) (0 1 0 1) (1 1 0 1) (0 0 1 1) (1 0 1 1) (0 1 1 1) (1 1 1 1) (0 0 0 0 0 0 0) (1 1 0 1 0 0 0) (0 1 1 0 1 0 0) (1 0 1 1 1 0 0) (1 1 1 0 0 1 0) (0 0 1 1 0 1 0) (1 0 0 0 1 1 0) (0 1 0 1 1 1 0) (1 0 1 0 0 0 1) (0 1 1 1 0 0 1) (1 1 0 0 1 0 1) (0 0 0 1 1 0 1) (0 1 0 0 0 1 1) (1 0 0 1 0 1 1) (0 0 1 0 1 1 1) (1 1 1 1 1 1 1) (0 0 0 0 0 0) (1 1 0 1 0 0) (0 1 1 0 1 0) (1 0 1 1 1 0) (1 1 1 0 0 1) (0 0 1 1 0 1) (1 0 0 0 1 1) (0 1 0 1 1 1) (NOTE) uses the encoder/decoder of original code

Modified Hamming Codes Examples GLONASS string structure time marker 85 84 9 8 2 1 77 data bits (9-85) parity bits (1-8) Original Hamming : m=7, n= 2m-1=127, n-k=m=7 (127,120), dmin=3 Expanding (even parity) : (128, 120), dmin=4 Shortening (reduce 43 information bits) : (128-43, 120-43) = (85,77) Hamming code(SEC/DED)

Modified Hamming Codes Examples NAVSTAR Data Format TLM 22 bits C 2 P 6 HOW 22 bits t 2 P 6 P 6 • • • 24 bits Word 1 Word 2 Word 5 • • • Original Hamming : m=5, n= 2m-1=31, n-k=m=5 (31,26), dmin=3 Expanding (even parity) : (32, 26), dmin=4 Shortening (reduce 2 information bits) : (32-2, 26-2) = (30,24) Hamming code (SEC/DED)

Expurgating of Hamming Codes : reducing the information bits, keeping the number of code bits the same Example : (7,4) Hamming (7,3) expurgated Hamming ge(X) = g(X)(X+1) ge(X) = (X3+X+1)(X+1) = X4+ X3+ X2+1 최소거리(dmin)는 1 증가 Expurgated code의 Hamming weight는 항상 짝수 CRC 부호

Cyclic Codes 1957, Prange Considerable inherent algebraic structure : various practical methods of decoding LFSR(linear feedback shift register) structure : encoder, syndrome generator, … Hamming, BCH, RS, . . .

Cyclic Codes Example (7,4) cyclic code 1 all zero 0000000 2 generator sequence 0001011 3 shift generator left 0010110 4 2nd shift 0101100 5 3rd shift 1011000 6 4th shift 0110001 7 5th shift 1100010 8 6th shift 1000101 9 sequence 2+3 0011101 10 shift sequence 9 0111010 11 2nd shift 1110100 12 3rd shift 1101001 13 4th shift 1010011 14 5th shift 0100111 15 6th shift 1001110 16 sequence 2+11 1111111 Generator polynomial g(x) = x 3 + x + 1

- Generator polynomial : g(X) = g0 + g1X + g2X2 + . . . + gn-kXn-k LFSR Encoder (n-k) stage LFSR encoder - Generator polynomial : g(X) = g0 + g1X + g2X2 + . . . + gn-kXn-k

LFSR Syndrome Generator For (n,k) linear cyclic code, - Generator polynomial : g(X) = g0 + g1X + g2X2 + . . . + gn-kXn-k - Received polynomial : r(X) = r0 + r1X + r2X2 + . . . + rn-1Xn-1

Error Detection Code (CRC) Why error detection code ? - Error detection capability < Error detection capability (오류검출불가 확률이 낮아야 하는 채널에 적합) - Cost effective solution (정정부호에 비해 구현이 용이하고 시스템이 간단)  CRC(cyclic redundancy check) 부호가 가장 널리 사용됨

Error Detection Capability Error detection capability and minimum distance - 오류의 수가 dmin 보다 항상 작을 경우 : 모든 오류를 항상 검출 - 오류의 수가 dmin 과 같거나 많을 경우에도 검출불가 형태를 가지는 경우를 제외하고는 모두 검출 가능함 (예) (7,4) Hamming code, dmin = 3 , (0000000)를 전송 - 오류의 개수가 3개 미만인 경우 : 모든 오류 검출 - 오류의 개수가 3개인 경우 : Hamming weight가 3인 부호는 7개 이므로 총 35 (7C3 = 35) 개의 오류 형태 중 7개 만이 검출되지 않고 나머지 28개는 모두 검출됨 - 오류의 개수가 5 혹은 6개 인 경우 모두 검출 가능

CRC(cyclic redundancy check) An expurgated Hamming Code 12-bit CRC 16-bit CRC (1) CRC-16 (2) CRC-CCITT 32-bit CRC

Generator Polynomials 12-bit CRC - g(X) = X12 + X11 + X3 + X2 + X + 1 = (X11 + X2 + 1)(X + 1) - 부호 길이 = (211 – 1) = 2047 - 정보비트 수 = 2047 – 12 = 2035 - 패리티 비트 수 = 12 - 최소거리(dmin) = 4

Generator Polynomials CRC - 16 - g(X) = X16 + X15 + X2 + 1 = (X15 + X + 1)(X + 1) - 부호 길이 = (215 – 1) = 32767 - 정보비트 수 = 32767 – 16 = 32751 - 패리티 비트 수 = 16 - 최소거리(dmin) = 4 - BISYNC

Generator Polynomials CRC - CCITT - g(X) = X16+X12+X5+1 = (X15+X14+X13+X4+X3+X2+X+1)(X+1) - 부호 길이 = (215 – 1) = 32767 - 정보비트 수 = 32767 – 16 = 32751 - 패리티 비트 수 = 16 - 최소거리(dmin) = 4 - XMODEM(file transfer protocol), Disk storage, SDLC

Generator Polynomials 32-bit CRC - g(X) = X32+X26+X23+ X22+X16+X12+X11+X10 +X8 +X7+X5+X4+X2+X+1 = (X31+X30+X29+ X28+X27+X26+X22+X15+X14+X13+X12+X11 + X9+ X8+ X6+ X5+ X3+ X2+1)(X+1) - 부호길이 = (231 – 1) = 2147483648 - 최소거리(dmin) = 4 - Ethernet 프레임 중 FCS(frame check sequence)에 CRC 비트 저장