비이진 극 부호를 위한 새로운 고정 심볼 선택 방법

Ⅰ. 서 론

Arikan에 의해 제안된 이진 극 부호(binary polar code)는 이진 입력 이산 무기억 채널(binary input discrete memoryless channel, BI-DMC)에서 채널 용량을 달성할 수 있는 최초의 부호이다^[1]. 극 부호는 5G NR(new radio) 의 제어 채널에서 표준 코드로 채택되었으며^[2], URLLC (ultra-reliable low-latency communication) 시나리오를 위한 채널 부호로 주목받고 있다. URLLC는 저지연을 요구하지만 이진 극 부호는 우수한 오류 정정 능력을 위해 복잡도 및 복호 지연이 높은 복호 방법을 사용한다^[3]. 이러한 문제를 해결하기 위해, 병렬 처리 방식을 복호기에 적용함으로써 복호 지연을 감소시키기 위한 여러 연구가 수행되어왔다^[4],[5]. 비이진 극 부호는 이진 극 부호에 비해 블록 오류율을 줄이는 이점이 있다^[6]. Arikan에 의해 제안된 이진 극 부호의 경우에 부호어의 길이는 대부분 2의 거듭제곱으로 국한되지만, 비이진 극 부호는 부호어의 길이를 보다 다양하게 구성할 수 있다는 이점이 있다.

채널 양자화 현상을 이용하는 극 부호는 고정 심볼의 위치를 선택하는 것이 매우 중요하다. 그러나 이진 극 부호와 달리, 비이진 극 부호의 고정 심볼 선택 방법은 잘 알려져 있지 않다. 본 논문에서는 비이진 극 부호의 새로운 고정 심볼 선택 방법을 제안한다.

이진 극 부호을 구성하기 위해, 이진 소거 채널(binary erasure channel, BEC)에서 Bhattacharyya 파라미터를 통해 각 분리 채널들에 대한 채널 용량을 정확히 추정하는 것이 가능하다는 것은 이미 잘 알려져 있는 사실이다. 그러나 가산성 백색 가우시안 잡음(additive white Gaussian noise, AWGN) 채널과 같은 유․무한 크기의 알파벳 채널들을 포함한 광범위한 범위의 채널의 경우, 각 분리 채널들에 대한 채널 용량을 정확히 추정하는 것은 매우 어렵기 때문에, 여러 가지 근사적 부호 구성 방법이 제안되었다^[1],[7],[8]. Arikan은 Bhattacharyya 파라미터의 추정을 기반으로한 근사적 부호 구성 방법을 제안하였다^[1]. 블록 오류 확률 P(ϵ)은 모든 정보 비트에 대한 Bhattacharyya 파라미터 $Z\left(W_N^{\left(i\right)}\right)$, i=1,2, … , N의 합인${\displaystyle \sum _{iϵA}Z\left(W_N^{\left(i\right)}\right)}$, A⊆1,2, …, N을 상계(upper bound)값으로 갖는다. 여기서, BLER (block error rate) 방정식을 통해 이는 비교적 더 정확하게 표현이 가능하다^[9]. 본 논문에서는 이진 극 부호를 구성하는 경우와 유사하게, 비이진 극 부호의 구성을 위해 BLER 방정식을 기반으로 새로운 고정 심볼 선택 방법을 제안한다. 본 논문에서 제안한 방법은 극 부호를 구성하는 일반적인 2×2 커널 외, 멀티 커널을 구성하는 극 부호에 대해서도 쉽게 적용이 가능하다는 이점이 있다.

본 논문의 Ⅱ장에서는 비이진 극 부호의 채널 분리 및 합성에 대해 설명하고 Ⅲ장에서는 BLER 방정식을 기반으로 한 고정 심볼 선택 방법을 제안한다. Ⅳ장에서는 Ⅲ장에서 제안한 고정 심볼 선택 방법을 기반으로 구성된 비이진 극 부호의 BLER 성능을 확인하고 이에 대해 분석하며 마지막으로 Ⅴ장에서는 본 논문에 대한 결론을 맺는다.

Ⅱ. 채널 양극화

2-2 채널 합성 및 분리

극 부호는 N개의 독립적인 BI-DMC(binary-discrete memoryless channel) 채널이 합성과 분리 과정을 통해 N이 증가할수록 채널 용량이 0 또는 1로 양극화되는 채널 양극화 현상을 이용하여 채널 용량을 달성하는 부호이다.

비이진 채널의 채널 합성은 이진 채널과 유사한 방식으로 이루어진다. 채널 합성은 독립적인 N개의 이산 무기억 채널 W를 재귀적으로 합성하여 길이 N의 합성 채널로 만드는 과정이다. 기존의 비이진 극 부호는 두 개의 독립적인 채널이 재귀적으로 합성해나가기에 길이 N은 2^r 꼴이 된다. 여기서 r은 임의의 정수이다.

채널 합성 과정을 살펴보면 가장 먼저 두 개의 독립적인 채널 W를 합성하여 채널 W₂가 만들어진다. 이때, 채널 W₂에 대한 천이 확률 W₂(y₁, y₂|u₁, u₂)은 독립적인 채널 W의 입력 u₁⊕ηu₂에 대한 출력 y₁에 대한 천이 확률과 채널 W의 입력 u₂에 대한 출력 y₂에 대한 천이 확률의 곱으로 식 (1)과 같이 계산된다.

$$W_2\left(\left.y_1,y_2\right|u_1,u_2\right)=W\left(\left.y_1\right|u_1\oplus \eta u_2\right)W\left(\left.y_2\right|u_2\right),$$

(1)

여기서 u_i (i=1,2, …, N)는 입력 메시지의 i번째 심볼을 뜻하며 y_i (i=1,2, …, N)는 수신된 i번째 심볼을 뜻한다. 또한, η는 유한체 (finite field) GF(2^m)의 원소이며, ⊕는 GF(2^m)의 모듈러 연산을 의미한다. 그림 1과 같이 두 개의 독립적인 채널 W₂를 합성하여 W₄를 만들며 이때 W₄에 대한 천이 확률은 식 (2)와 같이 계산된다.

$$\begin{array}{l}{W}_4\left(y_1^4\mid u_1^4\right)\hfill \\ =W_2\left(\left.y_1,y_3\right|u_1\oplus \eta u_3,u_2\oplus \eta u_4\right)W_2\left(\left.y_2,y_4\right|u_2,u_4\right)\hfill \\ =W\left(\left.y_1\right|u_1\oplus \eta u_2\oplus \eta u_3\oplus {\eta }^2{u}_4\right)W\left(\left.y_2\right|u_2\oplus \eta u_4\right)\hfill \\ W\left(\left.y_3\right|u_3\oplus \eta u_4\right)W\left(y_4\mid u_4\right)\hfill \end{array}$$

(2)

그림 1. | Fig. 1. 채널 합성 과정(N=4) | Channel combining phase (N=4).

Download Original Figure

채널 양극화의 두 번째 단계인 채널 분리는 합성 채널 W_N을 다시 N개의 채널 $W_N^{\left(i\right)}$, 1≤i≤N들로 분리하는 과정이다. 이 때 $W_N^{\left(i\right)}$는 식 (3)과 같이 수학적으로 계산된다.

$$W_N^{(i)}\left(y_1^N,u_1^{i-1}\mid u_i\right)={\displaystyle \sum _{u_{i+1}^N}\frac{1}{q^{N-1}}}{W}_N\left(y_1^N\mid u_1^N\right).$$

(3)

이러한 채널 합성과 채널 분리의 과정은 비이진 극 부호의 부호 및 SC(successive cancellation) 복호 과정과 대응되며 일반적인 비이진 극 부호의 SC 복호 과정은 알고리즘 1과 같다. 최종 계산된 N개의 분리 채널에 대해, GF(2^m)위의 모든 가능한 원소에 대응되는 천이 확률 중 가장 큰 확률 값에 대응되는 심볼 ${\widehat{u}}_i$가 최종 결정된다. 이 때, i가 고정 심볼 위치의 집합을 나타내는 집합 Α의 원소이면 송․수신단이 사전에 약속한 고정 심볼로 최종 결정된다.

Algorithm 1. Procedure of SC DECODING^[10].

Download Original Figure

Ⅲ. 제안하는 고정 심볼 선택 방법

이전 Ⅱ장으로부터 채널 양극화는 채널 합성과 분리를 통해 이루어짐을 알 수 있었다. 채널 분리는 송신단과 수신단이 약속한 고정 심볼값의 전송과 SC 복호기로 유사 구현이 가능하다. 채널 양극화를 통하여 부호율에 따라, 신뢰도가 높은 채널에는 정보 심볼을 전송하며 상대적으로 낮은 심볼에는 고정 심볼을 전송한다. 이때, 부호어를 구성하는 각각의 심볼들에 대응되는 채널의 신뢰도를 정확히 추정하는 것은 매우 중요하다.

본 장에서는 BLER 방정식을 기반으로 한 비이진 극 부호에 대한 고정 심볼 선택 방법을 제안한다. B_i는 i번째 심볼이 정확히 복호되지 않는 사건 ${\widehat{u}}_i\ne u_i$와 이전 심볼들이 정확히 복호될 사건 ${\widehat{u}}_1^{i-1}=u_1^{i-1}$의 결합 사건 (Joint Event)으로 정의한다. 여기서 u_i (i=1, 2, … N)은 소수와 소수의 거듭제곱의 크기를 갖는 유한체 GF(p^m)위의 원소이다. 또한, ϵ는 메시지 블록이 정확히 복호되지 않을 사건이고 ϵ^c은 ϵ의 여사건으로 정의한다. 블록 오류 사건 ϵ은 모든 가능한 사건 B_i들의 합집합으로 표현된다. 그러나 확률 $P\left({\widehat{u}}_i\ne u_i\right)$와 $P\left({\widehat{u}}_1^{i-1}=u_1^{i-1}\right)$는 서로 독립적이지 않기 때문에, P(B_i)를 추정하는 것은 매우 어렵다. 그러므로 사건 C_i와 $C_i^c$을 식 (4)와 같이 정의한다.

사건 C_i와 $C_i^c$의 확률 P(C_i)와 $P\left(C_i^c\right)$은 식 (5)와 같이 계산된다.

SC 복호 과정 중, 이전에 결정된 심볼들인 $u_1^{i-1}$이 정확하다는 가정하에 ${\widehat{u}}_i\ne u_i$일 확률 P(C_i)는 쉽게 얻어질 수 있다. 사건 ϵ^c의 확률 P(ϵ^c)은

로 계산된다. 이로부터 부호어가 정확히 복호되지 않을 확률 P(ϵ)은 식 (7)과 같이 계산된다.

P(C_i)는 i번째 심볼 이전에 결정된 심볼들인 $u_1^{i-1}$이 정확하다는 가정하에, i번째 분리 채널의 천이 확률을 정확히 구한 식이며, P(ϵ)은 비이진 극 부호의 BLER의 정확한 표현이다. 따라서, P(ϵ)을 0에 근접하도록 비이진 극 부호를 설계하면 오류정정률을 극대화시킬 수 있다. P(C_i)의 근사적 추정을 통해, P(ϵ)을 0에 근접하도록 비이진 극 부호를 설계할 수 있기에, P(C_i)를 정확히 추정하는 것이 중요하다. 추정된 N개의 P(C_i) 중 P(C_i)가 상대적으로 높은 심볼 인덱스 i에는 송․수신단이 알고 있는 고정 심볼을 실어 보내어, 해당 인덱스의 오류 확률 P(C_i)를 0이 되도록 만든다. 반대로 P(C_i)가 낮은 심볼 인덱스 i에는 정보 심볼을 실어 보냄으로써, 전체 블록오류율 P(ϵ)을 최소화할 수 있다. P(C_i)는 알고리즘 2와 같이 제안된 고정 심볼 선택 방법을 통해 근사적으로 추정이 가능하다.

Algorithm 2. Procedure of FROZEN SYMBOLS SELECTION.

Download Original Figure

본 논문에서 제안하는 고정 심볼 선택 방법은 알고리즘 2을 통해 구현이 가능하다. 우선 비이진 극 부호의 길이 N의 부호어에 고정 심볼들을 전송한다. 주어진 designed-SNR(designed-signal to noise ratio)에 대응되는 채널을 거쳐 수신된 길이 N의 벡터를 SC 복호한다. 이때, 일반적인 SC 복호와 달리 i번째 심볼을 결정할 때, 고정된 부호어를 전송하였으므로 이전 심볼들인 $u_1^{i-1}$를 정확히 결정할 수 있고 SC 복호를 통해 i번째 심볼 ${\widehat{u}}_i$이 결정된다. 만약 심볼 ${\widehat{u}}_i\ne u_i$이면 SER(symbol error rate) 벡터$V_1^N$의 i번째 원소값이 1만큼 증가한다. 따라서 주어진 샘플 횟수 S만큼 이러한 과정이 반복 수행된 후, 각 분리 채널의 SER값으로 이루어진 SER 벡터$V_1^N$을 구할 수 있다. 또한 SER 벡터$V_1^N$의 원소들을 샘플 횟수 S로 정규화한 $V_1^N$의 원소들로부터 P(C_i), i=1, 2, …, N이 근사적으로 추정된다. 이 때, designed-SNR은 RE_s/N₀로 정의되며, E_s는 심볼당 에너지, N₀는 잡음 전력 스펙트럼 밀도를 의미한다. 근사적으로 추정된 각 분리 채널들에 대한 P(C_i)에 대해, 추정된 P(C_i)값이 상대적으로 높은 N-K개의 분리 채널들에 대응하는 심볼 위치에는 고정 심볼을 전송하고 그 외의 K개의 분리 채널들에 대응되는 심볼 위치에는 정보 심볼을 전송함으로써 비이진 극 부호가 구성된다. 따라서, 본 논문에서 제안한 고정 심볼 선택 방법 적용 시, 비교적 정확한 방법으로 비이진 극 부호를 설계할 수 있다. 또한, 멀티 커널을 갖는 비이진 극 부호의 부호 및 SC 복호 과정과 2×2 커널을 갖는 비이진 극 부호의 부호 및 SC 복호 과정은 동일하기에^[11], 멀티 커널을 갖는 비이진 극 부호는 본 논문에서 제안한 고정 심볼 선택 방법 통해 설계가 가능하다는 이점이 있다. 더불어, 본 논문에서 제안한 고정 심볼 선택 방법을 적용할 때, designed-SNR은 중요하게 고려해야 할 파라미터이다. Designed-SNR 함수는 부호어의 길이, 부호율을 변수로 갖는다.

따라서, 이후 Ⅳ장에서는 제안한 고정 심볼 선택 방법으로 비이진 극 부호를 설계하여 여러 designed-SNR에 따른 블록 오율을 확인하고 분석한다.

Ⅳ. 실험 결과

본 논문의 모의실험에서는 Ⅲ장에서 소개한 방법으로 비이진 극 부호를 설계하여 블록 오율을 분석한다. Designed-SNR은 −10 dB에서 10 dB 사이의 정수값으로 설정한다. 부호어의 길이 N은 64, 256으로 설정하고 부호화율 R은 1/2, 1/4로 고려한다. 채널은 가산성 백색 가우시안 잡음 채널 그리고 샘플링 횟수는 10,000번을 고려한다. 또한 유한체는 소수의 거듭제곱인 GF(2⁴)을 고려하며 커널은 $\left[\begin{array}{cc}1& 0\\ \eta & 1\end{array}\right]$ 를 고려한다. 이때, η는 α⁵을 고려한다.

그림 2 및 그림 3의 실험 결과는 부호어의 길이 N이 64이며 부호율이 각각 1/2, 1/4인 경우의 블록 오율이다. 그리고 그림 4 및 그림 5의 실험 결과는 부호어의 길이 N이 256이며 부호율이 각각 1/2, 1/4인 경우의 블록 오율이다. 표 1은 블록 오율 10⁻³ 이하에서 상대적으로 우수한 블록 오율을 갖는 designed-SNR들을 나열한 것이다. 그림 2와 그림 4의 실험 결과를 통해 R이 1/2인 경우, designed-SNR을 −2, −1, 0, +1, +2, +3으로 설정하였을 때, 우수한 성능을 가지는 것을 확인 할 수 있다. 또한, 그림 3 및 그림 5의 실험 결과를 통해 R이 1/4 인 경우에는 designed-SNR을 −6, −3, −2, −1, 0으로 가정하였을 때 우수한 성능을 갖는 것을 확인할 수 있다. 이를 통해, R이 낮을수록 낮은 designed-SNR에서도 우수한 성능을 갖는 것을 확인할 수 있다.

그림 2. | Fig. 2. Designed-SNR에 따른 블록 오율 성능(N=64, K=1/2) | Block error rate performance according to designed-SNR (N=64, R = 1/2).

Download Original Figure

그림 3. | Fig. 3. Designed-SNR에 따른 블록 오율 성능(N=64, K=1/4) | Block error rate performance according to designed-SNR (N=64, R = 1/4).

Download Original Figure

그림 4. | Fig. 4. Designed-SNR에 따른 블록 오율 성능(N=256, K=1/2) | Block error rate performance according to designed-SNR (N=256, R=1/2).

Download Original Figure

그림 5. | Fig. 5. Designed-SNR에 따른 블록 오율 성능(N=256, K=1/4) | Block error rate performance according to designed-SNR (N=256, R=1/4).

Download Original Figure

또한, 그림 2~그림 5의 실험 결과에서 designed-SNR이 −2, −1, 0으로 설정하였을 때 모두 우수한 성능을 갖는 것을 확인할 수 있다.

따라서, 실험 결과를 통해, 본 논문에서 제안한 고정 심볼 선택 방법으로 비이진 극 부호를 설계할 때, designed-SNR은 부호율과 부호어의 길이를 변수로 갖는 함수임을 알 수 있다. 또한, designed-SNR을 어떻게 설정하느냐에 따라 블록 오율의 성능이 확연히 상이한 양상을 띠는 것을 확인할 수 있기에, designed-SNR을 어떻게 설정하는지는 비이진 극 부호 설계에 있어 매우 중요하게 고려되어야 할 파라미터임을 알 수 있다.

Ⅴ. 결 론

본 논문에서는 비이진 극 부호의 고정 심볼 선택 방법을 제안하였다. 비이진 극 부호의 P(C_i)를 실험적으로 추정 시, 어떤 designed-SNR을 선택하는지는 매우 중요한 요소이며, designed-SNR 함수는 부호화율 및 부호어의 길이를 변수로 갖는 함수이다. Ⅳ장의 실험에 따라, designed-SNR을 −2 dB, −1 dB 그리고 0 dB로 설정하였을 경우 모두 우수한 블록 오율을 가지는 것을 알 수 있었다.

차후에는 다양한 부호어의 길이 및 부호화율에 따른 우수한 성능을 갖는 designed-SNR을 체계적으로 갖는 방법에 대한 연구가 필요할 것이다.