Channel Coding

- 참조: Digital Modulation Python Plot:  https://pysdr.org/content/digital_modulation.html

 

chnnel coding 은 방대한 영역을 보여주는 무선통신의 범주로서, 정보의 정량화, 저장 및 통신에 관한 스터디를 포함하는 정보이론(information theory)을 의미한다. Forward Error Correction 줄여서 FEC 로 알려진 channel coding 에 대해서 알아보자. 특히 parity를 체크하여 1 비트 정보의 오류를 알아내는 Hamming code 사례를 소개한다. 그밖에 Turbo 코드라든지 LDPC 코드는 어떤 것인지 정도만 알아보도록 하자.

 

무선채널은 워낙 노이즈가 많아서 송신해 오는 심볼들을 완전하게 수신하기 대단히 어렵다. 이미 네트워킹 분야에서 수신단에서의 에러를 감지하기 위한 CRC(cyclic redundancy checks) 란 기법에 익숙할 것이다. channel coding 의 목적은 통신 에러를 감지하여 바로 잡는 것이다. 

만약 에러에 대한 여지를 허용한다면 링크가 끓어지지 않는 선에서 좀 더 고차적인 변조 통신 스킴을 사용해서 송신할 수 있을 것이다. 

동일한 수준의 노이즈를 타는 QPSK 와 16QAM constellation diagram의 가시적 예를 고려해 보자. QPSK는 심볼당 2비트를 제공하는 반면에 16QAM은 심볼당 4비트로서 2배의 데이터 비율을 보여준다. 아래 그림의 QPSK에서는 심볼들 간의 간섭이 없음을 알 수 있다. 즉 심볼들이 에러가 없이 전달되어 수신된다. 반면에 16ㅃQAM에서는 클러스터간의 오버랩이 심하게 나타나는데 이는 심볼 수신에 에러가 많다는 점을 나타낸다.

적어도 TCP 통신에서는 CRC가 실패할 경우 재전송해야 하는 상황이 발생한다. 만약 A가 B에게 메세지를 보낸다면 B로 하여금 A에게 다시 정보를 재요청하게끔 하고 싶지는 않을 것이다. channel coding 의 목적은 redundancy(여분의 정보)를 보내는 것인데 그 여분의 정보라는 것은 에러흫  포함한 패킷, 재전송 및 데이터 누락 양을 줄이기 위한 일종의 failsafe 에 해당한다. 다음 그림을 참조하면서 송수신 체인의 어느 부분에서 channel coding 필요한지 살펴보자.

Types of Codes

위 그림에서 encoding  작업이 2회 일어남을 알 수 있다. 첫번째 source encoding은 컴퓨터에서 zip 작업을 하는 것 처럼 입력 데이터를 압축하여 크기를 줄이는 과정이다. 두번째 channel  encoding 에서는 reduncy를 추가하여 그 크기가 압축된 입력 데이터 보다는 상대적으로 커지게 된다.

 

channel coding 을 수행하기 위해서 error correction code를 사용하자. 이 코드는 송신해야 할 비트들이 주어졌으면 실제로 어떤 비트들을 보내야 하는가 문제이다. 가장 기본적인 코드로서 반복형 코드가 있다. 보내야 할 비트를 한 줄에서 N번 반복하는 유형이다. 3회 반복형 코드 사례를 살펴보자.

 만약 '10010110' 을 전송해야 한다면 '111000000111000111111000'이 전송되어야 하는 것이다. 어떤 코드는 길이가 일정한 블록형 코드를 사용하며 반면에 데이터 길이가 임의의 값을 가지는 스트림형 코드 즉 Convolution code도 있다.

그밖에 하드나 SSD 또는 메모리에 데이터를 쓰거나 불러 오는 등의 작업에서도 마찬가지로 절대로 에러가 발생해서는 안되기때문에 회사별로 지적 재산권에 해당하는 channel coding 이 컨트롤러에 채용된다. 과거 CD 같은 경우는 표준화된 기법이 적용되는 Reed-Solomon coding  이 알려져 있다.

 

Codes-Rate

모든 에러 교정 기법은 어던 형태로든 redundancy 를 전제로 한다. 즉 100비트 정보를 보내려면 100비트 그 이상의 정보를 보내야 한다는 점이다. Codes-Rare는 전체 보내는 비트 수에 대한 실제 정보의 비트 수와의 비율을 뜻한다. 3회 반복형 코드의 Codes-Rate은 (1/3)이 된다.

 

Modulation & Coding

낮은 SNR값 에서는 저차원의 변조기법 QPSK 를 사용할 수 있으며 SNR값이 높을 경우에는 초당 보다 많은 비트 정보를 받기 위해서 고차의 256QAM을 사용할 수 있을 것이다. channel coding 도 마찬가지이다. 낮은 SNR 값이라면 codes-rate 가 낮은 것을 원할 것이며 높은 SNR 값 조건하에서는 codes-rate 가 거의 1.0에 가까운 것을 원할 것이다.

 

현대의 통신 체계에서는 MCS 로 불리는 변조와 코딩이 복합된 방식이 사용되고 있다. 즉 MCS 는 SNR 레벨에 맞춰 변조와 코딩 스킴을 지정한다. 특히 현대 무선 통신의 경우에는 실시간으로 MCS 를 적응제어 한다고 보면 된다. 수신파트는 송신파트에 channel quality에 대한 피드백을 channel quality 가 변하기 전 수ms 내에 보내 송신파트와 공유해야 한다. 이러한 적응형 과정에 의해서 LTE, 5G 및 WiFi는  최고의 통신처리 수준에 도달할 수 있게 된다.

다음의 그림은 사용자와 먼 거리에 의해서 변동하는 MCS 중계국 타워를 가시화 해 보여주고 있다.

다음 그림은 적응형 LTE 에 있어서 SNR 값 변동에 따른 통신 처리량과의 관계를 보여 주고 있다.

 

 

참조: Hamming Code Example

http://www.cs.ucc.ie/~jvaughan/archres/notes/hamming-example.pdf

 

Hamming Code

블록형 코드의 간단한 사례로 Hamming Code 예를 들어 보자. 이는 오래 전에 통신 모뎀에서 흔히 사용되던 기법으로서 1950년 경 당시 Bell Lab 기술자인 Hamming에 의해 창안되었다. 1950년대 그때 당시 통신의 선구자였던 Claude Shannon 도 Bell Lab에서 근무하였다는 점은 인상적이다. hanning은 펀치카드 천공에 의해 low level 코드를 작성하던 시절의 에러로 짜증나는 시절의 경험에서 이 기법을 제안하였다. 

 

다음표에서 Codeword 는 redundancy 포함 전송하려는 정보이다. 즉 전송하려는 정보는 0000 1010 이며 나머지 4개의 r1,r2,r3,r4는 정해줘서 채워 보내야 할 redundancy 요소들이다. redundacy 요소들의 위치는 2의 승으로서 현재의 12 비트 전송 문제에서는 1,2,4,8 방식으로 정해진다.

아래 표의 bit positions 쪼개기(break down) Bit No.1은 비트 위치 1,3,5,7,9에 영향을 미친다. 이는 쪼개기 분석에서 1 을 포함하는 좌측의 비트 위치 값을 확인하면 된다.

  - parity bit r1:  1,3,5,7,9 위치에 있는 값들 즉 r1+0+0+0+1 = r1+1 --> 이 값이 짝(even)이려면 r1 = 1,

  - parity bit r2:  2,3,6,7,10 위치에 있는 값들 즉 r2+0+0+0+0 = r1 --> 이 값이 짝(even)이 되려면 r2 = 0,

  - parity bit r3:  4,5,6,7,12 위치에 있는 값들 즉 r4+0+0+0+0 = r4 --> 이 값이 짝(even)이 되려면 r3 = 0,

  - parity bit r4:  8,9,10,11,12 위치에 있는 값들 즉 r4+1+0+1+0 = r+2 --> 이 값이 짝(even)이 되려면 r4 = 0.

 

이와같이 r1,r2,r3,r4 parity 값들이 결정되면 "1000 0000 1010" 데이터를 전송할 수 있다.

만약에 6번 위치의 값이 노이즈로 인해서 "1000 0100 1010" 을 전송받았다면 parity bit 계산을 수행해 보면 r2 와 r3 parity 계산이 틀리게 되므로 이때는 6번 비트의 값을 "1"에서 "0" 으로 고쳐야 한다.

 

만약에 7번 위치의 값이 노이즈로 인해서 "1000 0010 1010" 을 전송받았다면 parity bit 계산을 수행해 보면 r1, r2 와 r3 parity 계산이 틀리게 되므로 이때는 7번 비트의 값을 "1"에서 "0" 으로 고쳐야 한다.

 

Hamming Code 는 전송 데이터 중 1비트의 에러가 포함된 경우에는 원래의 정확한 값을 찾아서 고칠 수 있다. 2비트까지는 에러 검출은 가능하지만 고칠 수는 없음에 유의하자.

 

Soft 와 Hard Decoding

수신파트에서는 decoding 이전에  변조가 먼저 읽어 나게 된다. 변조기는 어떤 심볼을 보냈는지 최상의 추정치를 제공하며 즉 soft한 값을 출력할 수 있다. BPSK 경우에 변조기는 정확하게 "1" 또는 "0" 이 아닌  0.3423 Eb 또는  -1.1234 Eb  값을 제공한다. 반면에 Hard Decoding 에서는 "1" 또는 "0"만이 사용된다.

 

물론 Soft Decoding 이 수신한 정보를 마음껏 사용할 수 있기때문에  일견 유리해 보이기도 하지만 실제로는 대단히 복잡함이 뒤따른다. 앞에서 언급했던 Hamming 코드는 Hard 적인 결정 방법이며 이와는 반대로 Convolution 코딩 기법이 Soft 한 기법으로 볼 수 있다.

 

Shannon 의 공식

 

에러 없이 얼마난 많은 양의 정보를 보낼 수 있는지 Shannon 의 용량 공식을 살펴보자. channel 의 용량은 (1+SNR) 의 로그 값에 비례함을 볼 수 있다.

이 공식을 가로축에 dB 단위로 작도해 보자. SNR 값이 낮을 경우에 channel 용량이 작을 수밖에 없음을 알 수 있다.

전송 시스템 용량을 극대화 하기 위해서는 SNR 값이 상당히 높아질 수 있도록 각종 노이즈를 퇴치할 수 있어야 할 것이다.

State of the Art Codes

 

현재 실전에서사용중인 코딩 스킴 Turbo 와 LDPC를 살펴보자.

   - Turbo codes, used in 3G, 4G, NASA’s spacecraft.

   - LDPC codes, used in DVB-S2, WiMAX, IEEE 802.11n.

이 두 종류의 코드는 Shannon 의 용량 한계 공식에 접근하는 결과를 보여준다. 한펴 ㄴhamming  코드와 여타의 간단한 코드들은 Shonnon 용량 공식 근처에 오지도 못한다. 연구관점에서 코드 자체를 개량할 여지는 거의 없으며 현재의 연구 초점은 decoding 에 있어서 컴퓨팅 효율을 올린다든지 또는 적응형 피드백을 개선하는 정도에 머무른다.

 

LDPC(Low-density parity-check ) 코드는 아주 효율적인 선형 블록 코드의 일종이다. 이 코드는 1960년대에 Robert G. Gallager의 MIT 박사논문으로 출판되었다. 이 코드는 실행이 대단히 복잡하므로 저자의 나이가 89세가 되어 이 블로그 글을 쓰는 시점인 1990년대까지 무시되었었다. 물론 이 업적으로 많은 상을 받았으며 Turbo 코드와는 반대로 특허 출원이 되지 않았기때문에 오픈 소스로 남아 있다.

 

Turbo 코드는 convolutional 코드이며 2개 이상의 간단한 convolutional 코드들과 그들을 역어주는 코드들로 구성된다. 이 코드는 프랑스인이 발명하여 1991년에 특허 출원하여 2013년에 특허권이 소멸되었다.  Qualcomm 이 3G 구현을 위한 CDMA 적용에 관심을 가졌었다.

 

Under Construction ...