[논문]최소거리가 확장된 극 부호의 연속 제거 리스트 복호 성능

류대현; 김재열; 김종환; 김상효

doi:10.7840/kics.2013.38c.1.109

최소거리가 확장된 극 부호의 연속 제거 리스트 복호 성능
Performance of Successive-Cancellation List Decoding of Extended-Minimum Distance Polar Codes 원문보기

한국통신학회논문지. The Journal of Korea Information and Communications Society. 통신이론 및 시스템, v.38C no.1, 2013년, pp.109 - 117

류대현 (성균관대학교 정보통신대학 통신 및 부호이론 연구실) , 김재열 (삼성전자 DMC연구소) , 김종환 (성균관대학교 정보통신대학 통신 및 부호이론 연구실) , 김상효 (성균관대학교 정보통신대학 통신 및 부호이론 연구실)

초록
AI-Helper

극 부호(polar codes)는 광범위한 이진 입력 이산 무기억 채널(binary input discrete memoryless channel: BI-DMC)에서 채널 용량에 달성하는 것이 이론적으로 증명된 최초의 채널부호이다. 하지만 유한한 길이를 갖는 극 부호는 연속 제거 리스트(successive-cancellation list: SCL) 복호기에서 오류마루(error floor)가 발생하는 문제점이 있다. 선행 연구에 따르면 이 오류마루 현상은 극 부호에 오류 검출 코드(error detection codes) 중 하나인 CRC(Cyclic Redundancy Check) 부호를 연접했을 때 효과적으로 낮출 수 있는 것으로 알려져 있다. 본 논문에서는 외부 부호(outer codes)를 사용하지 않고 극 부호와 RM(Reed-Muller) 부호의 생성 행렬 연관성을 이용하여 기존 극 부호보다 확장된 최소거리를 갖는 극 부호를 제안한다. 그리고 제안된 극 부호와 CRC 부호를 연접한 극 부호의 성능을 비교한다.

Abstract ▼ AI-Helper

Polar codes are the first provable error correcting code achieving the symmetric channel capacity in a wide case of binary input discrete memoryless channel(BI-DMC). However, finite length polar codes have an error floor problem with successive-cancellation list(SCL) decoder. From previous works, we can solve this problem by concatenating CRC(Cyclic Redundancy Check) codes. In this paper we propose to make polar codes having extended-minimum distance from original polar codes without outer codes using correlation with generate matrix of polar codes and that of RM(Reed-Muller) codes. And we compare performance of proposed polar codes with that of polar codes concatenating CRC codes.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

따라서 복호 성능은 최소거리의 지배를 받게 된다. 그러므로 본 논문에서는 SC 복호를 가정하고 생성된 기존의 극 부호 생성 규칙을 수정하여 극 부호의 최소거리를 확장하는 기법을 제안한다. 이렇게 생성된 단일 극 부호의 성능을 CRC가 연접된 극 부호의 성능과 비교한다
본 논문에서는 RM 부호와 극 부호의 생성 행렬 연관성을 이용하여 SC 복호를 가정하여 생성하는 기존 극 부호화 규칙을 수정하여 SCL 복호기에 적합한 최소거리 확장 극 부호화 방법을 제안하였다. 모의실험을 통해 제안한 방법을 사용한 단일 극 부호의 성능을 CRC 부호를 연접한 극 부호의 성능과 비교하였다.
본 논문에서는 극 부호와 RM(Reed-Muller) 부호의 생성 행렬의 연관성을 이용하여 CRC 부호와 같은 외부부호(outer code)를 사용하지 않고 기존의 극 부호화 규칙으로 설계된 부호보다 최소거리가 확장된 극 부호 설계 방법을 제안한다. 그 후 제안한 극 부호의 SCL 복호 성능을 확인한다.
본 절에서는 채널 양극화를 야기하는 채널 합성과 분리 과정에 대해 알아본다. N=2ⁿ(n은 양의 정수)를 만족하는 N에 대하여 N개의 채널 W가 병렬적으로 존재하는 것을 W^N, N개의 독립적인 채널 W의 채널 합성으로 인해 생성된 합성 채널은 W_N, 채널 분리 과정으로 생성된 분리 채널은 #(1≤i≤n)로 표기한다.

제안 방법

본 논문에서는 극 부호와 RM(Reed-Muller) 부호의 생성 행렬의 연관성을 이용하여 CRC 부호와 같은 외부부호(outer code)를 사용하지 않고 기존의 극 부호화 규칙으로 설계된 부호보다 최소거리가 확장된 극 부호 설계 방법을 제안한다. 그 후 제안한 극 부호의 SCL 복호 성능을 확인한다. 또한 이 결과를 토대로 CRC 부호를 연접한 극 부호와 SCL 복호기 사이의 관계를 분석한다.
5이며 SCL 복호기의 L=16, 32이다. 극 부호는 E_b/N₀ = 2dB 채널에서의 밀도진화를 이용하여 설계하였다. 제안된 최소거리 확장 극 부호의 성능과 비교하기 위해 CRC 부호를 연접한 극 부호를 함께 제시하였다.
그 후 제안한 극 부호의 SCL 복호 성능을 확인한다. 또한 이 결과를 토대로 CRC 부호를 연접한 극 부호와 SCL 복호기 사이의 관계를 분석한다.
이번 장에서는 기존 극 부호의 복호 성능과 확장된 최소거리를 갖는 극 부호의 복호 성능을 비교한다. 모의실험을 위해 이진입력 부가백색 정규잡음 채널(BI-AWGNC)을 고려하였다. 극 부호의 N=32, 1024, 2048, R=0.
본 논문에서 제안된 극 부호는 SC 복호기와 최대우도 복호기의 특성을 함께 갖는 SCL 복호기의 특성에 맞도록 기존 극 부호의 설계 방법을 따르면서 최소거리가 확장된 부호이다. 채널 교체는 기존 극 부호의 최소거리를 확장할 수 있지만, 동시에 오율이 높은 분리 채널이 I에 포함되어 SC 복호의 성능 열화를 야기한다.
본 논문에서는 기존 극 부호의 부호화 규칙을 따르면서 극 부호의 최소거리가 증가되도록 부호를 설계한다. 극 부호의 최소거리는 다음과 같이 정의할 수 있다^[2].
그림 3은 SC 복호기와 SCL 복호기의 성능을 비교하고 있다. 비교를 위해 이진입력 부가백색 정규 잡음 채널(binary input AWGN channel: BI-AWGNC)을 고려한다. 극 부호의 부호 길이 N=2048, 부호율 R=0.
5이며 SCL 복호기의 L=16, 32이다. 사용된 극 부호는 밀도 진화를 이용하여 E_b/N₀=2 dB에 최적화되도록 설계되었다. 그림 3에서 확인할 수 있듯이 극 부호의 SCL 복호성능은 SC 복호 성능보다 우수하지만 오류마루가 발생하는 문제점이 있다.
그러므로 본 논문에서는 SC 복호를 가정하고 생성된 기존의 극 부호 생성 규칙을 수정하여 극 부호의 최소거리를 확장하는 기법을 제안한다. 이렇게 생성된 단일 극 부호의 성능을 CRC가 연접된 극 부호의 성능과 비교한다
이번 장에서는 기존 극 부호의 복호 성능과 확장된 최소거리를 갖는 극 부호의 복호 성능을 비교한다. 모의실험을 위해 이진입력 부가백색 정규잡음 채널(BI-AWGNC)을 고려하였다.
극 부호는 E_b/N₀ = 2dB 채널에서의 밀도진화를 이용하여 설계하였다. 제안된 최소거리 확장 극 부호의 성능과 비교하기 위해 CRC 부호를 연접한 극 부호를 함께 제시하였다.
이 개념을 이용한 지니 SC 복호기는 #, #을 완벽히 알고 있을 때 u_i를 복호하는 복호기이다. 지니 SC 복호기를 통해 실제 복호에 사용될 각 분리 채널의 용량을 계산한다. 극 부호는 SC 복호기로 분리 채널을 실현하기 위해 송신기와 수신기가 모두 알고 있는 고정비트(frozen bit)를 이용한다.

데이터처리

본 논문에서는 RM 부호와 극 부호의 생성 행렬 연관성을 이용하여 SC 복호를 가정하여 생성하는 기존 극 부호화 규칙을 수정하여 SCL 복호기에 적합한 최소거리 확장 극 부호화 방법을 제안하였다. 모의실험을 통해 제안한 방법을 사용한 단일 극 부호의 성능을 CRC 부호를 연접한 극 부호의 성능과 비교하였다. 대부분의 부호 길이에서는 제안된 극 부호의 성능이 CRC 부호를 연접한 극 부호의 성능과 근접한 결과를 보였다.

성능/효과

L=32일 때 블록 오율 10–4기준으로 제안된 극 부호의 복호 성능이 기존 극 부호의 복호 성능보다 약 1dB 이상 개선된다.
모의실험을 통해 제안한 방법을 사용한 단일 극 부호의 성능을 CRC 부호를 연접한 극 부호의 성능과 비교하였다. 대부분의 부호 길이에서는 제안된 극 부호의 성능이 CRC 부호를 연접한 극 부호의 성능과 근접한 결과를 보였다. 또한, 부호 길이 N=32, 부호율 R=0.
대부분의 부호 길이에서는 제안된 극 부호의 성능이 CRC 부호를 연접한 극 부호의 성능과 근접한 결과를 보였다. 또한, 부호 길이 N=32, 부호율 R=0.5인 경우 제안된 극 부호의 성능은 CRC 부호 연접 극 부호보다 블록 오율 10^–3기준 으로 0.8dB 더 좋은 성능을 보이고 CRC 부호 연접 극 부호는 기존의 극 부호의 성능을 개선하지 못하는 것을 확인하였다. 하지만 최소거리를 확장하기 위해 교체한 채널의 비율이 높아지면 SC 복호기의 규칙에 어긋나는 분리 채널이 부호화에 사용되는 비율이 높아져 동일한 크기의 L일 때 성능 열화가 발생하는 경우가 생긴다.
반면 제안된 극 부호의 성능은 CRC를 연접한 극 부호보다 오율 10–3기준으로 Eb/N0는 약 0.8dB 개선된다.
제안된 극 부호의 복호 성능은 Eb/N0= 1.75dB 이하의 영역에서 16비트 CRC 부호를 연접한 극 부호의 복호 성능보다 나은 성능을 보이지만 Eb/N0= 1.75dB 이후에는 성능 역전이 일어난다.
그림 7은 N=2048인 극 부호의 복호 성능을 보여준다. 제안된 극 부호의 최소거리는 기존 극 부호의 최소거리인 16보다 두 배 확장되었다. L=32일 때 블록 오율 10^–4기준으로 제안된 극 부호의 복호 성능이 기존 극 부호의 복호 성능보다 약 1dB 이상 개선된다.
하지만 L=32인 제안된 극 부호는 최소거리를 확장하기 위해 선택한 채널이 기존 극 부호의 채널보다 상대적으로 높은 오율을 갖는 채널로 작용하여 Eb/N0= 1.75dB 이후로 기존 극 부호보다 열화된 성능을 보인다.

질의응답

핵심어	질문	논문에서 추출한 답변
	극 부호란?	극 부호(polar codes)는 광범위한 이진 입력 이산 무기억 채널(binary input discrete memoryless channel: BI-DMC)에서 채널 용량에 달성하는 것이 이론적으로 증명된 최초의 채널부호이다. 하지만 유한한 길이를 갖는 극 부호는 연속 제거 리스트(successive-cancellation list: SCL) 복호기에서 오류마루(error floor)가 발생하는 문제점이 있다.
	SCL 복호기를 사용한 유한한 N을 갖는 극 부호의 복호 성능은 어떠한 문제점이 있는가?	SCL 복호기는 L개의 부호어 후보를 생성하여 이 중 전송된 부호어를 추정하는 복호기로 SC 복호기보다 향상된 성능을 보인다. 하지만 SCL 복호기를 사용한 유한한 N을 갖는 극 부호의 복호 성능은 오류 마루(error floor)가 발생하는 문제점이 있다. Tal과 Vardy의 연구에 의하면 이와 같은 문제점은 오류검출부호(error detecting code) 중 하나인 CRC(Cyclic Redundancy Check) 부호를 극 부호와 연접하여 효과적으로 해결할 수 있으며 CRC 부호를 연접한 극 부호의 SCL 복호 성능은 터보 부호나 LDPC 부호에 근접한 성능을 보인다.
	SC 복호기와 SCL 복호기의 성능의 비교를 위해 어떠한 것을 고려하였는가?	그림 3은 SC 복호기와 SCL 복호기의 성능을 비교하고 있다. 비교를 위해 이진입력 부가백색 정규 잡음 채널(binary input AWGN channel: BI-AWGNC)을 고려한다. 극 부호의 부호 길이 N=2048, 부호율 R=0.

참고문헌 (16)

K. Yang, "Covering radius of Reed-Muller codes," in Proc. KICS Int. Conf. Commun. 1995 (KICS ICC 1995), pp. 215-218, Jeju Island, Korea, Jan. 1995.
D. Ryu, J. Y. Kim, J. -H. Kim, and S. -H. Kim, "Performance of list decoding of minimum distance-extended polar codes," in Proc. KICS Int. Conf. Commun. 2012 (KICS ICC 2012), pp. 445-446, Jeju Island, Korea, Jun. 2012.
C. E. Shannon, "A mathematical theory of communication," Bell System Tech. J., vol. 27, no. 1, pp. 379-423, 623-656, Jul./Oct. 1948.

상세보기
E. Arıkan, "Channel polarization: a method for constructing capacity- achieving codes for symmetric binary- input memoryless channels," IEEE Trans. Inform. Theory, vol. 55, no. 7, pp. 3051-3073, Jul. 2009.

상세보기
R. Mori and T. Tanaka, "Performance of polar codes with the construction using density evolution," IEEE Commun. Lett., vol. 13, no. 7, pp. 519-521, Jul. 2009.

상세보기
N. Goela, S.B. Korada and M. Gastpar, "On LP decoding of polar codes," in Proc. IEEE Inform. Theory Workshop (ITW), pp. 1-5, Dublin, Ireland, Aug./Sep. 2010.
E. Arıkan, "A performance comparison of polar codes and Reed-Muller codes," IEEE Commun. Lett., vol. 12, no. 6, pp. 447-449, Jun. 2008.

상세보기
N. Hussami, R. Urbanke and S.B. Korada, "Performance of polar codes for channel and source coding," in Proc. IEEE Int. Symp. Inform. Theroy, pp. 1488-1492, Seoul, Korea, Jun./Jul. 2009.
I. Tal and A. Vardy, "How to construct polar codes," 2011, from arXiv:1105.6164v2
E. Sasoglu, E. Telatar and E. Arıkan, "Polarization for arbitrary discrete memoryless channels," in Proc. IEEE Inform. Theory Workshop (ITW), pp. 144-148, Taormina, Italy, Oct. 2009.
E. Sasoglu, "Polar codes for discrete alphabets," in Proc. IEEE Int. Symp. Inform. Theory (ISIT), pp. 2137-2141, Cambridge, MA, Jul. 2012.
M. Seidl and J.B. Huber, "Improving successive cancellation decoding of polar codes by usage of inner block codes," in Proc. Int. Symp. Turbo Codes and Iterative Inform. (ISTC), pp. 103-106, Brest, France, Sep. 2010.
I. Tal and A. Vardy, "List decoding of polar codes," 2012, from arXiv:1206.0050v1
R. Mori and T. Tanaka, "Performance and construction of polar codes on symmetric binary-input memoryless channels," in Proc. IEEE Int. Symp. Inform. Theroy, pp. 1496-1500, Seoul, Korea, Jun./Jul. 2009.
D. E. muller, "Application of boolean algebra to switching circuit design and to error correction," IRE Trans. Electronic Computers, vol. EC-3, no. 3, pp. 6-12, Sep. 1954.
I. Reed, "A class of multiple-errorcorrecting codes and the decoding scheme," IRE Trans, Inform. Theory, vol. 4, no. 4, pp. 39-44, Sep. 1954.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증