Channel Coding

 

Channel Coding

Tx에서 Rx로 데이터를 보내는 과정에서, Channel의 상황에 따라, bit에 Error가 생길 수 밖에 없다. 이 때, Error를 Detection (검출)하고, Correction (정정)해서 원래 보내려고 했던 Data (bit)를 복구하기 위해 진행하는 절차를 Channel Coding이라 한다. Channel Coding에서는 Transmission Power와 Bandwidth 소모를 최소로 하면서, Decoding 확률을 높이고, 시스템의 Complexity를 최소로 하기 위한 다양한 알고리즘들이 제안되 었다. 기본적인 구조는 우리가 보내려고 했던 기존 bit들에 Error를 Detecting하고 Correction하기 위한 추가 비트를 붙이고 Encoding하여 보내는 방식이다. Channel Coding에서 제시된 알고리즘들은 이런 추가 비트들을 어떻게 생성하고, 어디에 붙일지를 최적화시키는 과정이다.

이 때, 추가 비트들은 기존에 보내려고 했던 Data가 아니라, Decoding을 위해서 만들어진 'Overhead'다. 즉, 효율성 측면에서 이런 Overhead의 비중은 적을수록 좋고, 추가 비트를 얼마나 추가해서 보냈는지를 나타내는 수치로 Code Rate이라는 개념을 사용한다. 식으로 표시하면,

Code Rate (R) = 내가 보내려는 Bits 수 / Channel Coding을 위해 추가된 비트를 포함한 전체 Bits 수

이다. 즉, Code Rate가 1에 가까울수록, 추가 비트의 비중이 작고, 내가 원래 보내려고 했던 Data bit의 길이가 길다는 뜻이기 때문에 효율적인 전송이다. 하지만, 그만큼 Bit가 Decoding될 확률은 낮아지게 된다.

Bit가 얼마나 복구되는지에 대한 성능 분석을 위해 Coding Gain (부호화 이득)이라는 개념이 있다. 가장 일반적인 AWGN Channel에서 Eb/N0의 감소량으로 정의되는 Coding Gain은, 추가 비트를 붙임으로써 얼마나 Decoding 확률이 높아졌는가를 나타낼 수 있다. 그러면 어떤 절차를 통해서 Channel Coding을 진행하고, Channel Coding에는 어떤 알고리즘이 있는지5G에서 사용되고 있는 Channel Coding 방식을 통해 알아보자.

 

Channel Coding Procedure

Channel Coding은 크게 4가지 Step이 있다. Tx에서 진행하는 순서와 역순으로 Rx에서 진행하게 된다.

• Parity Bit나 Cyclic Redundacny Check (CRC)를 붙여, Block Coding을 하고, 'Error Detection'할 수 있도록 하는 단계
• Redundancy bit 붙이고, 'Error Correction'하도록 하는 단계 / (Forward Error Correction) FEC
• 지정한 Rate를 맞춰주기 위해 puncturing이나 Repetition을 하는 'Rate matching'
• Bit error가 일정 부분에 쏠려서 (Error Burst) Decoding 확률이 낮아지는 것을 막기 위해 bit를 섞어주는 Interleaving

이 있다. 각 Step에 대해 조금더 자세히 다뤄보도록 한다.

 

1) Error Detection

위에서 볼 수 있듯이, Channel Coding에서는 Error Detection과 Correction Mechanism이 나눠져 있다. Detection을 하는 가장 간단한 방법으로는 Parity Bit나 CRC를 붙여서 Block Coding을 하는 방식이 있다. Rx 입장에서는 이런 추가 비트들(Redundancy Bits)를 이용해서 Error를 Detection하게 된다.

 CRC는 다항식을 통해서 전송하려는 Bit에 문제가 있는지 없는지를 찾아내는 방법, Parity Bits는 0 or 1의 홀수, 짝수 여부를 가지고 Data의 Error를 Detection하는 방법이다. 다항식이 홀짝 갯수 세는것보다는 어렵기 때문에, CRC의 연산량이 더 많은 대신에, Partiy Bits로는 잡아낼 수 없는 Error Detection도 할 수 있다. 

 

2) Error correction

 Correction을 위한 단계인 Forward Error Correction (FEC) 단계를 거치고 나면, k bits의 data bits와 n-k bits의 Redundancy bits가 모여서 총 n bits의 Codeword가 생긴다. 길이가 같은 두 문자열을 대조해서 bits가 많이 겹치는 문자열로 인식하는 Hamming Distance 방식등이 쓰인다. 하지만, 여기서 문제점은 Bits의 길이가 길어지면, Computation Power와 Complexity가 증가하게 된다. 따라서, 짧은 bits를 가지는 Control Information이 아니라, 긴 bits를 가지는 일반적인 Data들은 이런 이슈를 우선적으로 해결해야 한다. 이를 위해, 하나의 커다란 문제를 해결하는 것이 아니라, 작은 문제 여러 개로 나눠서 병렬적으로 문제를 해결하는 방법이 연구되었고, 이 중 하나가 5G에서 Data를 주고 받을 때 쓰이는 LDPC다. 이에 대해서는 조금 더 자세히 뒤에서 다루도록 한다.

 

3) Rate Matching

Error Correction을 위해 Encoding을 한 후에, PHY Layer의 Bit Rate을 맞춰주기 위해서, Rate Matching을 한다. Encoding 한 후의 Bit가 Bit Rate에서 요구하는 Bit보다 작으면 Bit를 반복하는 Bit Repetition을, 요구하는 Bit보다 크면 Bit를 자르는 Bit Puncturing을 한다. Bit를 Repetition을 해서 굳이 자원을 낭비하는 것으로 보일 수 있지만, 이를 통해 더 적은 Power로 안정성을 확보할 수도 있다.

 

4) Interleaving

마지막 Procedure로, Bit의 순서를 섞어주는 Interleaving이 있다. 이는 데이터의 일정부분에 Error가 몰려서, Correction의 성능이 떨어지는 Error Burst를 방지하기 위함이다. 한 번 Error가 생겼다는 것은 해당 Channel이 안 좋은 환경에 놓여있을 가능성이 크기 때문에, 뒤이어 Error가 연이어 생기는, Error Burst가 생긴다. 이 때, Bit의 순서를 섞어주면, 한 부분에서 Error가 나도, 연관된 Bit도 함께 Error가 발생할 확률이 줄어들기 때문에 Correction 성능을 올릴 수 있다.

 

Low Density Parity Check (LDPC) Coding

5G 글에서 소개하겠지만, LTE와 비교했을 때, NR은 Error Correction을 진행하는 부분에서 Channel Coding 방식이 바뀌기 때문에 이를 통해서 Correction의 한 예를 들어보고자 한다. 5G에서는 Data를 주고 받을 때는 LDPC Coding을, Control 메시지를 주고받을 때는 Polar Coding이라는 방식을 선택한다는 점이 LTE와 비교했을 때, 5G NR의 Channel Coding에서 바뀐 부분이다. 그러면, 많은 Channel Coding 방식 중에 LDPC에 대해서 조금 더 다뤄보도록 한다.

 이를 설명하기 위한 Parity Bit의 간단한 예로, 짝수 Parity Bit 방식에서는 1의 갯수가 짝수개가 되어야 한다. 즉, 기존 Bit로 0을 보내면 Parity Bit로 0을 보내야 한다. 만약 기존 Bit 가 0이 도착했는데, 'Parity Bit가 1이면, 기존 Bit가 1이어야하는데 잘못 전달됐구나' 라는 것을 알 수 있는 방식이다. 그런데, Bit 여러 개가 있는 1개의 Set를 일반적인 Parity Bit로 해결하려고 하면, 문제가 생긴다. 2 bits 이상이 동시에 잘못 도착하면 Parity Bit 갯수가 짝수인지 홀수 인지로 이를 판단할 수 없기 때문이다. 이를 위해 여러 Bit가 묶인 Set를 겹쳐서 Parity Bit를 할당하는 Overlapping Parity 방식을 사용한다. 많은 Channel Coding 방식이 이 Overlapping parity를 어떤 방식으로 구성하고 어떻게 겹치게 할지에 대한 알고리즘을 다르게 한다.

 LDPC는 Set로 묶이는 Bit를 줄이고, Overlapped된 Bit도 줄임으로써 Set의 수를 늘린다. 이를 조금 더 알기 쉽게 쓰면, 작은 문제 (작은 Set) 를 여러 개 (많은 Set) 만드는 방식이다.

 LDPC는 Parity 검사를 위한 Parity Matrix가 대부분 0이고 소수의 1로 구성되어 있기 때문에, Low Density Parity Check (LDPC)라는 이름이 붙었다. 나중에 딥러닝에서도 다루겠지만 현재 컴퓨터의 구조는 큰 문제 하나를 푸는 것보다, 작은 문제 여러 개를 나눠서 푸는 병렬처리에 강하다. 따라서, LDPC는 Complexity가 낮기 때문에 큰 데이터를 보내는데 적합하여 Data Channel에 주로 사용된다.