논문번호 12-37A-07-02 한국통신학회논문지 '12-07 Vol.37A No.07 길쌈부호를수평부호로가지는곱부호의복호를위한유한연판정데이터결합 양필웅, 박호성 *, 홍석범 *, 전보환 *, 노종선 *, 신동준 ** Finite Soft Decision Data Combining for Decoding of Product Codes With Convolutional Codes as Horizontal Codes Pilwoong Yang, Hosung Park *, Seokbeom Hong *, Bohwan Jun *, Jong-Seon No *, Dong-Joon Shin ** 요 약 본논문에서는곱부호를위한연판정데이터의결합을이용한복호기법을유한비트연판정만을적용하여사용할수있도록새로운연판정데이터의결합법칙을제시한다. 기존의무한연판정을이용한복호기법은복잡한 tanh 연산에기반을두고있으므로높은연산복잡도와함께하드웨어에적용하기어려운단점이있다. 따라서기존복호기법에서이용되는연산들을분석하여작성한간단한연산테이블을이용하여복호하는방법을제시한다. 또한연판정데이터를적용하기용이한길쌈부호를곱부호의수평부호로이용하였을때연판정데이터의결합방식을찾는방법을제시하고모의실험을통해성능을검증한다. 제안된알고리듬은 4비트유한연판정을적용한길쌈부호를곱부호의수평부호로이용하였을때무한연판정을적용한경우의성능에근접함을보였다. Key Words:channel coding, convolutional codes, product codes, soft decision data, Viterbi algorithm ABSTRACT In this paper, we propose feasible combining rules for a decoding scheme of product codes to apply finite soft decision. Since the decoding scheme of product codes are based on complex tanh calculation with infinite soft decision, it requires high decoding complexity and is hard to practically implement. Thus, simple methods to construct look-up tables for finite soft decision are derived by analyzing the operations of the scheme. Moreover, we focus on using convolutional codes, which is popular for easy application of finite soft decision, as the horizontal codes of product codes so that the proposed decoding scheme can be properly implemented. Numerical results show that the performance of the product codes with convolutional codes using 4-bit soft decision approaches to that of same codes using infinite soft decision. Ⅰ. 서론무선통신시스템에서전송되는신호는다른신호와의간섭, 페이딩및전파방해등의효과로인해왜곡된다. 이러한신호왜곡현상을효과적으로 해결하기위해순방향오류정정 (forward error correction, FEC) 방식이사용된다. 전진오류정정방식은정보시퀀스에잉여비트를추가하여송신함으로써수신측에서이를이용해오류를검출하고정정하는방식을말한다. 길쌈부호 (convolutional 본연구는방송통신위원회의차세대통신네트워크원천기술개발사업 (KCA-2012-08-911-04-003) 과 2012 년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (No. 2012-0000186) 주저자 : 서울대학교전기 컴퓨터공학부및뉴미디어통신공동연구소, yangpw@ccl.snu.ac.kr, 정회원 * 서울대학교전기 컴퓨터공학부및뉴미디어통신공동연구소, lovepark98@ccl.snu.ac.kr, 정회원, fousbyus@ccl.snu.ac.kr netjic@ccl.snu.ac.kr, 비회원, jsno@snu.ac.kr, 종신회원 ** 한양대학교전자통신컴퓨터공학부, djshin@hanyang.ac.kr, 종신회원논문번호 :KICS2012-04-188, 접수일자 :2012 년 4 월 14 일, 최종논문접수일자 :2012 년 6 월 13 일 512
논문 / 길쌈부호를수평부호로가지는곱부호의복호를위한유한연판정데이터결합 codes) 는이러한방식을위해사용되는오류정정부호로서우수한오류정정능력과더불어연판정 (soft decision) 복호를적용하기용이하므로비터비복호기와함께위성 이동통신에널리이용되어진다. 곱부호 (product codes) 는여러개의부호어가일렬로연접된부호로서두개이상의짧은길이의블록부호들을연결하여긴블록부호를구성하는데이용된다. 작은최소해밍거리 (minimum Hamming distance) 를갖는짧은부호들을결합하여큰최소해밍거리를갖는긴부호를생성할수있으므로곱부호또한다양한분야에널리응용되어왔다 [1,2]. 이러한곱부호를위한새로운복호기법이최근에제안되었다 [3]. 이는곱부호의부호어행렬 (codeword matrix) 내의수평부호 (horizontal codes) 를기준으로오류가발생한수평부호어들의연판정데이터를결합하여결과적으로하나의수평부호어를기준으로두개의독립적으로수신한연판정데이터를얻어냄으로써성능이득을얻는기법이다. 이기법의성능및복잡도는하나의부호어행렬내에서발생한수평부호어오류개수에영향을받으므로특히높은신호대잡음비 (signal-to-noise ratio, SNR) 에서적은복잡도증가만으로큰성능이득을얻을수있다. 이때수평부호로이용되는부호는선형이고오류검출능력이있는어떠한부호도사용가능하며, 수직부호 (vertical codes) 로사용되는부호들은 SPC 부호나해밍부호와같은간단한부호가사용될수있다. 앞서제안된복호기법은적은복잡도증가로성능이득을나타내는반면, 무한한연판정데이터를이용한로그우도비율 (log-likelihood ratio, LLR) 덧셈과 tanh 연산에기반을두고있으므로실제하드웨어에서구현되기에어려움이있다. 따라서 3비트, 4비트등의유한연판정만을허용하는환경에서이복호기법을간단하게적용할수있는방법에대한고찰이필요하다. 본논문에서는이복호기법에이용되는두연산을분석하여유한비트연판정데이터만을이용할때복잡한계산을거치지않고간단한연산테이블을적용하여결합법칙을나타낼수있는방법을제시한다. 간단한대수부호들이수직부호로이용될수있으나여기서는가장명료하게기법을적용할수있는단일패리티체크 (single parity-check, SPC) 부호를기준으로한다. 본논문의구성은다음과같다. 2장에서는최근 그림 1. 곱부호의부호어행렬구조 Fig 1. Structure of a codeword matrix of a product code 에소개된곱부호의복호기법에대해설명한다. 3 장에서는앞서소개한복호기법에유한비트연판정을적용하고, 이를토대로 4장에서는유한비트연판정을이용한길쌈부호를수평부호로사용할때의복호기법을유도한다. 5장에서모의실험을통해성능을확인하고마지막으로 6장에서결론을맺는다. Ⅱ. 곱부호를위한복호기법 이장에서는 [3] 에서소개된곱부호를위한복호기법에대해소개한다. 이복호기법은동일한수평부호어를위한두개의독립적으로수신된연판정데이터를결합하는것을기반으로한다. 수신한곱부호의부호어행렬내에오류가발생한수평부호어만을결합하므로이용되는수평부호는선형이고오류검출능력이있어야한다. 부호의길이를 ( ), 정보비트수를 ( ), 최소해밍거리를 min ( min ) 이라할때, 각각 min, min 의파라미터를갖는두종류의블록부호, 을고려한다. 이러한부호 와 을각각수직부호, 수평부호로가지는곱부호의구조는그림 1과같다. 곱부호의부호어행렬이그림 1과같이 행렬이라할때, 이부호는 개의수평부호어가쌓여있는행렬이된다., 가 번째수평부호어를,, 가 를전송했을때채널로부터수신한값을연판정한데이터를의미한다하자. 연판정데이터 는 의수신값으로부터얻어진 LLR값으로이루어진벡터이다. 곱부호의수직부호로 SPC 부호가이용되면수직부호의패리티체크행렬 는다음과같이나타내진다. 513
한국통신학회논문지 '12-07 Vol.37A No.07 (1) 따라서패리티체크행렬의성질에의해다음식이성립한다. (2) 즉, 하나의수평부호어 는나머지다른수평부호어들의이진합 (exclusive OR, XOR) 과동일하다. 의연판정데이터 를결합하기위해아래와같은식을이용한다. 두개의부호어가합해진결과값의 LLR값은각각의부호어의 LLR값을이용하여다음과같이계산되어진다 [4]. tanh tanh tanh (3) 임의의한수평부호어를 라하고이의 LLR 값 들로이루어진벡터를 라하자. 이때부호어 가정상적으로복호된부호어라면이의각비트의 LLR값 은 가 1일때, 0일때 가된다. 이처럼결합하는두개의부호어중하나의부호어를이미알고있을때 (3) 의 LLR 결합은아래와같이간단히부호변화로나타낼수있다. if if (4) 위와같은특성들을이용하여제시된복호방법은곱부호의부호어행렬내의수평부호어오류개수에따른정정기법이다. 총 개의수평부호어중오류가발생한수평부호어의개수가 일때, 세부적인복호과정은아래와같다. 2.1. 인경우 : 부호어행렬내의수평부호어오류개수가 1개인경우, 수직부호어로사용된 SPC 부호의성질에따라이수평부호어는부호어행렬내의다른모든수평부호어들의합과같다. 즉, 오류가발생한수평부호어를 이라하면아래와같은식이성립한다. (5) 을제외한모든수평부호어들은정상적으로 복호되었으므로이들의이진합으로 을항상복호할수있다. 따라서 인경우언제나복호가가능하다. 2.2. 인경우 : 부호어행렬내의수평부호어오류개수가 2개인경우, 오류가발생한수평부호어들을각각, 이라하면 SPC 부호의성질에따라아래의식이성립한다. (6) 부호어행렬내에두개이상의수평부호어오류가존재하므로 인경우와같이경판정데이터만을이용한복호는사용할수없다. 따라서 (6) 에대한연판정데이터계산을고려한다. 의 LLR벡터는 으로주어지고, (6) 의우변의 LLR벡터는아래와같이주어진다. (7) 위식에서 을제외한 은 이모두정상적으로복호된수평부호어들이므로, 벡터내의모든성분이 혹은 값을가진다. 따라서 (7) 의결과값은 (4) 에언급하였듯 벡터내의모든성분들에간단한부호변화만일어난결과, 즉모든성분이 혹은 값을가지는벡터가된다. 이렇게얻어진결과값과 의연판정데이터 은 (6) 의좌 우변이동일하므로동일한부호어에대한연판정데이터라생각할수있다. 결과적으로 (6) 의좌변 을기준으로볼때, LLR벡터 뿐아니라 (7) 의결과도 의연판정데이터로간주할수있으므로이두 LLR벡터를단순히더하여얻어진연판정데이터를이용해서 을재복호함으로써높은성능이득을얻을수있다. 재복호에성공한다면곱부호의부호어행렬에남아있는수평부호어오류개수는 1개이므로 인경우로돌아가항상복호가가능해지고이로써부호어행렬은모두복호된다. 2.3. 인경우 : 3개이상의수평부호어오류를부호어행렬이가지고있는경우오류를포함한수평부호어를각각 이라한다. 마찬가지로아래 514
논문 / 길쌈부호를수평부호로가지는곱부호의복호를위한유한연판정데이터결합 의식이성립한다. (8) 인경우와마찬가지로 을위한두연판정데이터는다음과같다. (9) 은정상복호되었으므로 벡터내의모든성분은 혹은 이다. 따라서 을위한두번째연판정데이터는채널에서얻은 을 (3) 에의해계산한 을 (4) 에따라부호변화함으로써얻어낼수있다. 이두 LLR벡터를더한결과를이용하여 을재복호함으로써성능이득을얻을수있고, 성공시부호어행렬에남은수평부호어오류개수가하나씩감소하므로계속해서재복호를시도할수있다. 사용하는각양자화레벨의대푯값들이 0을기준으로대칭이라면대푯값을그대로더하는것이결과적으로신뢰도를더하는것이된다. 따라서부호어행렬내의수평부호어오류개수 가 2일때는각비트의유한비트연판정데이터, 즉양자화레벨의대푯값들을더한결과를복호함으로써좀더높은신뢰도의결과를얻을수있다. 허나 가 3 이상일때는 가 2인경우와달리, 더해야하는두개의연판정데이터중하나의신뢰도가더저하된상황이므로두연판정데이터를그대로더해서는안된다. 즉 Ⅱ.3절에서 에해당하는 (9) 에나타낸두연판정데이터를더할때 LLR값은그대로더하는것이최대비율결합 (maximal ratio combining, MRC) 을만족하지만, 연판정데이터를각양자화레벨의대푯값으로사용하는유한비트연판정상황에서는덧셈을아래와같이보정해줌으로써 MRC을만족할수있다. (10) Ⅲ. 유한비트연판정을위한결합법칙이장에서는 Ⅱ장에서설명된기존의복호방식을유한비트연판정만이허용된환경에적용하는방법에대해설명한다. 앞선복호기법에사용되는연산은하나의수평부호어를나타내는두개의연판정데이터를합치는 LLR 덧셈계산과, 부호어행렬내의오류개수가 3개이상일때사용되는 (3) 의 LLR tanh 계산으로두가지이다. 따라서두가지계산이유한비트연판정에서어떻게표현되는지도출함으로써결합법칙을구성할수있다. 무한연판정에서연판정데이터를 LLR값을이용한것과달리유한비트연판정에서는하드웨어에서표현할수있는한계가존재하므로모든실수범위의수신값을해당비트에맞게양자화 (quantization) 하고각양자화레벨의대푯값으로부터 LLR을얻는것으로가정하였다. 3.1. LLR 합연산 Ⅱ장에서언급했듯이, 부호어행렬내의수평부호어오류개수 가 2 이상인경우연판정데이터 LLR값의합연산이필요하다. LLR 합연산은근본적으로해당하는비트의신뢰도를더하는과정이므로유한비트연판정에서 이때, 는오류가발생한수평부호어들이고, 는 비트의연판정데이터인각양자화레벨의대푯값, 는채널표준편차를나타낸다. 은 연산에의해변경된표준편차를의미한다. 수평부호어들사이의연산은각비트마다독립적으로이루어지므로 는수평부호어의길이내부의한지점이다. tanh 연산을거친결과인 는다음절에서계산된다. 3.2. LLR tanh 연산부호어행렬에 3개이상의수평부호어오류가발생했을때는 LLR tanh 연산이필요하다. 따라서두개의연판정데이터, 즉두개의대푯값들의 tanh 결과가어느양자화레벨에존재하는지판정을내리는것이목적이다. 먼저, (3) 의 tanh 연산이어떤성질을가지는지확인한다. 결합할비트를각각, 라하고이들의연판정데이터는각각,, 결합결과값을 라한다. ⅰ) 의부호는 와 의부호가같을때양수, 다를때음수가된다. tanh 연산의의미는두개의부호어를이진합 515
한국통신학회논문지 '12-07 Vol.37A No.07 연산한결과의신뢰도를나타낸다. 이진합연산은두비트의부호가같을때양수, 다를때음수가되므로연판정데이터의부호도마찬가지로설정된다. ⅱ), 이다. 연판정데이터의절대값은신뢰도의크기나타낸다. 즉, 신뢰도가높은데이터와신뢰도가낮은데이터를결합했을때결과의신뢰도는둘중신뢰도가낮은데이터보다높을수없다. 100% 신뢰도를가진데이터와낮은신뢰도를가진데이터를결합했을때결과의신뢰도는낮은신뢰도와동일하다. 이는 (4) 에서보인결과와같다. ⅲ) 일때 이성립한다. ⅱ) 에서연산결과는항상신뢰도가감소함을언급하였으므로이제신뢰도의감소크기를고려한다. 신뢰도 가있을때, 의신뢰도의감소크기는결합되는데이터의신뢰도 가높을수록적다. 가 0이면 는 0, 가 이면 는 가된다. 따라서위의식이성립한다. ⅳ) 일때 이성립한다. ⅲ) 에서하나의신뢰도가고정되어있을때결과값의신뢰도의감소크기는결합되는데이터의신뢰도가높을수록적다는것을보였다. 이번에는신뢰도가높은데이터둘을결합한결과와신뢰도가낮은데이터둘을결합한결과의신뢰도감소크기를비교한다. 의우도비율 (likelihood ratio, LR) 을 라하면, (3) 에서 LR 값은아래와같이계산된다. log 이므로, 는다음과같다. log log log log log (11) (12) 이면 이고, (12) 에서신뢰도가큰두데이터를결합한결과는신뢰도가작은 그림 2. 양자화레벨 A 와레벨 B 를 연산한결과범위 Fig 2. Result range of combining Level A and B 두데이터를결합한결과보다신뢰도감소크기가더크다는것을확인할수있으므로위의식이만족한다. 여기서중요한점은신뢰도감소크기가 가커질수록점점커지다가일정해진다는점이다. 신뢰도감소크기의최댓값은 (12) 에의하면 log가되며, 이는 LLR값이므로채널수신값으로변환하면채널표준편차가 인가산백색가우시안잡음 (additive white Gaussian noise, AWGN) 채널일때 log가된다. 이를이용하여유한비트연판정에사용되는비트수가정해졌을때간단한연산이가능한 db범위를계산할수있다. 위의성질들을이용하여 와 로부터 를계산한다. 무한연판정과는다르게유한비트연판정은 비트연판정일때 개의양자화레벨이존재하므로, 두개의양자화레벨을 연산했을때결과값이어느양자화레벨로결정되는지판단해야한다. 그림 2는양자화레벨 A와 B가결합되었을때의결과값이존재할수있는범위를나타낸다. 결과범위의좌측경계는양자화레벨 A와레벨 B의좌측경계를결합한결과로, 우측경계는각양자화레벨의우측경계를결합한결과로결정된다. 또한 ⅳ) 의성질에의해결과범위의크기는한양자화레벨의크기를 라했을때 를넘을수없으므로, 어떠한결과범위도최대두양자화레벨에만걸쳐존재할수있다. 따라서이러한결과범위가두양자화레벨에걸쳐존재한다면좀더높은확률을가진, 즉결과범위의중간값을포함하고있는양자화레벨이결정레벨이될것이다. 여기서고려할점은양자화레벨 A와레벨 B의 연산이항상낮은신뢰도를갖는양자화레벨 A 로결정되는경우이다. 위의 ⅳ) 에서언급하였듯신뢰도감소크기의최댓값은채널표준편차가 인 AWGN 채널일때 log이다. 만약이신뢰도감소크기의최대치가한양자화레벨의크기 의절반을넘지않는다면, ⅰ) ⅳ) 의성질에따라어떠한두양자화레벨 A와 B를 연산한결과 516
논문 / 길쌈부호를수평부호로가지는곱부호의복호를위한유한연판정데이터결합 는항상낮은신뢰도를갖는양자화레벨로결정될것이다. 신뢰도감소크기의최댓값은 에따라달라지므로, 계산에의해이러한상황이발생하는 db 구간을찾아낼수있다. 이외의경우아래와같은과정을거쳐연산테이블을작성할수있다. ⅰ) 타깃이되는 db의채널표준편차 를계산한다. ⅱ) 각양자화레벨의대푯값을설정하고, ( 일반적으로중간값 ) 설정된대푯값을 LLR로변환한다. AWGN 채널에서 으로쉽게변환된다. ⅲ) 변환된 LLR값들로가능한모든대푯값의쌍에대해 (3) 의연산을수행한다. ⅳ) ⅲ) 의결과값들을 로재변환하고, 변환한결과가위치하는양자화레벨을결정레벨로설정한다. 이때 ⅲ) 에서 (3) 의연산을수행한결과값들은신뢰도의크기가감소하였으므로변경된채널표준편차 을갖지만, ⅳ) 에서재변환시 이아닌 를다시이용함으로써두연판정데이터를더하는과정인 (10) 에서언급한 MRC를아래와같이만족할수있다. (13) 부호로하는곱부호의복호방법을알아본다. 4.1. 3비트연판정길쌈부호를수평부호로하는곱부호 3비트연판정을이용하는길쌈부호의경우일반적으로이용되는양자화레벨의크기는 이다. 개의양자화레벨이존재하므로이의대푯값들을각각 7, -5, -3, -1, 1, 3, 5, 7 으로설정하였고, 이는각비트의연판정데이터로사용된다. 부호어행렬내에오류가발생한수평부호어의개수 가 1이면수직부호인 SPC 부호의성질에따라항상복원가능하다. 가 2인경우대푯값으로설정된연판정데이터를더한값을복호함으로써신뢰도를향상시키는효과를얻을수있으며, 가 3 이상인경우 Ⅲ장에제시한방법을이용하여타깃으로하는 db의표를작성하여간단히복호할수있다. 가장먼저고려할점은 (3) 의 계산을해야할경우, 어떠한두양자화레벨을 연산하더라도항상낮은신뢰도를갖는양자화레벨에놓이게되는 단순 연산 이가능한구간을찾아내는것이다. 앞서언급하였듯이구간은최대신뢰도감소크기가구간의길이의절반이하로수렴하는 db구간을찾아내는것과동일하다. 즉, 아래와같이나타난다. max (15) (14) 의최댓값은 Ⅲ장에서 log임을밝혔으므로한양자화레벨의크기 를고려하면 의범위는아래와같이정리된다. log (16) 결과적으로계산후얻은연판정데이터와원래의연판정데이터를더함으로써 MRC를만족하는연산을수행하였다. 이렇게얻어진연판정데이터를이용하여해당수평부호어를재복호함으로써 Ⅱ장의복호기법을이용할수있다. Ⅳ. 길쌈부호를이용한곱부호복호이장에서는 Ⅲ장에언급한결합법칙을이용하여 3비트, 4비트연판정을적용한길쌈부호를수평 따라서 (16) 은, 일때성립한다. 실제로부호가적용되는채널환경이이범위를벗어나는경우는드물기때문에표 1 과같은단순 연산이가능하다. 표 1은 7 7 을대푯값으로갖는 3비트연판정데이터를 연산한결과를나타낸다. 결과적으로 3비트유한연판정을이용한길쌈부호를수평부호로이용했을경우 3개이상의수평부호어오류가부호어행렬내에발생했을때 연산의결과값은, 부호는연산할모든연판정데이터의 517
한국통신학회논문지 '12-07 Vol.37A No.07 표 1. 단순 연산결과 Table 1. Simple combined results -7-5 -3-1 1 3 5 7-7 7 5 3 1-1 -3-5 -7-5 5 5 3 1-1 -3-5 -5-3 3 3 3 1-1 -3-3 -3-1 1 1 1 1-1 -1-1 -1 1-1 -1-1 -1 1 1 1 1 3-3 -3-3 -1 1 3 3 3 5-5 -5-3 -1 1 3 5 5 7-7 -5-3 -1 1 3 5 7 부호의곱으로, 절대값은모든연판정데이터중절대값이가장작은데이터의절대값으로결정되어진다. 이렇게얻은결과와다른하나의연판정데이터를 (14) 와같이더하여재복호함으로써성능이득을얻을수있다. 4.2. 4비트연판정길쌈부호를수평부호로하는곱부호 4비트의경우양자화레벨의개수가 3비트보다두배늘어나므로 로줄어든다. (15) 에의해, 이경우표 1에나온단순 연산이가능한구간은 이다. 따라서 Ⅲ장에서언급한대로적용하는채널의 db에따라적합한 연산표를작성할수있다. 표 2 표 5는 0.5 4.0dB의범위에서 0.5dB단위마다얻어낸연산테이블의예시이며, 각양자화레벨의대푯값은 15 15로설정되었다. 연산결과의부호는두연판정데이터의부호가같으면양수, 다르면음수이므로절대값만표로나타내었다. 음영으로처리된부분은표 1의단순 연산결과와다른결과값임을나타낸다. 채널의정보를미리알고있다고가정할때 4비트연판정의경우위와같은연산테이블을이용해단순 연산보다더욱정밀한연산을수행할수있다. 마찬가지로이렇게얻어낸결과와다른연판정데이터를더한결과를이용하여재복호를시도할수있다. 표 2. 4 비트연판정 연산결과, =0.5-1dB Table 2. Combined results of 4-bit soft decision at =0.5-1dB 15 13 11 9 7 5 3 1 15 13 11 11 9 7 5 3 1 13 11 11 9 9 7 5 3 1 11 11 9 9 7 7 5 3 1 9 9 9 7 7 5 5 3 1 7 7 7 7 5 5 3 3 1 5 5 5 5 5 3 3 1 1 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 표 3. 4 비트연판정 연산결과, =1.5dB Table 3. Combined results of 4-bit soft decision at =1.5dB 15 13 11 9 7 5 3 1 15 13 11 11 9 7 5 3 1 13 11 11 9 9 7 5 3 1 11 11 9 9 7 7 5 3 1 9 9 9 7 7 5 5 3 1 7 7 7 7 5 5 3 3 1 5 5 5 5 5 3 3 3 1 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 표 4. 4 비트연판정 연산결과, =2dB Table 4. Combined results of 4-bit soft decision at =2dB 15 13 11 9 7 5 3 1 15 13 11 11 9 7 5 3 1 13 11 11 9 9 7 5 3 1 11 11 9 9 7 7 5 3 1 9 9 9 7 7 5 5 3 1 7 7 7 7 5 5 5 3 1 5 5 5 5 5 5 3 3 1 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 Ⅴ. 모의실험결과이장에서는모의실험을통하여제안된유한비트연판정을적용했을때의성능을보이고, 무한연판정을그대로사용했을때의성능과비교하여보인다. 모의실험에는 3비트 4비트테일바이팅 (tailbiting) 길쌈부호가수평부호로, SPC 부호가수직부호로적용된곱부호가사용되었다. 부호율을높이기위해사용된테일바이팅길쌈부호를복호하기위해랩-어라운드비터비복호기 (wrap-around Viterbi decoder) 가이용되었다 [3]. 수평부호어로사용된길쌈부호는부호율 1/2 길쌈부호에서 12/23 518
논문 / 길쌈부호를수평부호로가지는곱부호의복호를위한유한연판정데이터결합 표 5. 4 비트연판정 연산결과, =2.5-4dB Table 5. Combined results of 4-bit soft decision at =2.5-4dB 15 13 11 9 7 5 3 1 15 13 11 11 9 7 5 3 1 13 11 11 11 9 7 5 3 1 11 11 11 9 9 7 5 3 1 9 9 9 9 7 7 5 3 1 7 7 7 7 7 5 5 3 1 5 5 5 5 5 5 3 3 1 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 양식의삭제행렬 (deleting matrix) 을이용하여천공 (punctured) 된부호율 12/23인길쌈부호가사용되었으며, 부호어 메시지길이는 (552,288), 구속장길이 (constraint length ) 는 9가사용되었다. 수평부호어복호를위한랩-어라운드비터비복호기의반복횟수 (iteration) 는두번으로설정하였다. 수직부호로이용된 SPC 부호는부호어 메시지길이가 (24,23) 로설정되어부호율은 23/24이고, 결과적으로곱부호의총부호율은 1/2 이다. 실험환경은 AWGN 채널을가정하였다. 그림 3은 3비트유한연판정을적용한길쌈부호를수평부호로갖는곱부호의성능을보여준다. 곱부호 # 뒤의숫자는복호를시도하는수평부호어의최대오류개수를말한다. 즉, 곱부호 #3은부호어행렬내의수평부호어중 3개이하의수평부호어에만오류가발생했을시복호를시도하고 4개이상의수평부호어에오류가발생하면복호를포기한다. 좀더많은수의수평부호어오류를복호시도하는것이물론좋은성능을보이나, 그만큼복잡도도증가하는결과를가져온다. 이때최대로고려하는수평부호어오류개수의증가에따른성능증가폭이 가높아짐에따라점점감소하는것도동시에관찰된다. 곱부호 #2, #3, #4, #24의성능이점점높은 로갈수록수렴해가는것을볼수있는데, 이는 가높아질수록곱부호의부호어행렬내의많은수의수평부호어에서오류가발생할확률이점점낮아지기때문이다. 성능비교를위해동일한부호율을가진단일길쌈부호가같이비교되었으며곱부호가더좋은성능을보이는것을확인하였다. 그림 4는 3비트, 4비트유한연판정길쌈부호와무한연판정길쌈부호를각각수평부호로갖는곱 그림 3. 3 비트유한연판정테일바이팅길쌈부호를수평부호로가지는곱부호의성능 Fig 3. Performance of a product code with 3-bit soft decision TB convolutional codes as horizontal codes 그림 4. 유한비트연판정결합과무한연판정결합시곱부호의성능비교 Fig 4. Comparison of product codes with finite and infinite soft decision 부호들을비교하였다. 3비트유한연판정에는표 1 의단순 연산이사용되었고 4비트유한연판정에는표 2 표 5의연산테이블이적용되었다. 무한연판정에는채널에서수신한값을그대로연산에이용하였고 (3) 을이용하여 연산을수행하였다. 결과적으로, 4비트유한연판정만을이용한길쌈부호의곱부호가무한연판정을이용한길쌈부호의곱부호의성능에근접함을확인하였다. 또한, 매번연판정데이터의결합을시도할때마다 (3) 의복잡한 tanh계산을수행해야하는무한연판정의성능에근접한성능을간단한연산테이블만으로수행함으로써복잡도를낮출수있었다. 519
한국통신학회논문지 '12-07 Vol.37A No.07 Ⅵ. 결론본논문에서는곱부호를위한연판정데이터의결합을이용한복호기법을유한비트연판정만을적용하여사용하도록새로운연판정데이터의결합법칙을제시하였다. 무한연판정을이용한높은연산복잡도를요구하는기존의복잡한 tanh 연산을분석하여, 유한비트연판정만을이용한연산테이블을작성하는방법이제시되었다. 또한연판정데이터적용의용이성때문에널리이용되고있는길쌈부호를곱부호의수평부호로이용하였을때, 제안된방법을적용하여연산테이블을작성하였다. 모의실험을통해확인한성능은, 제안된알고리듬에의해작성한연산테이블로복호를진행한 4비트유한연판정의길쌈부호를수평부호로갖는곱부호의성능이복잡한연산을그대로수행한무한연판정의곱부호의성능에근접함을확인하였다. References [1] C. Yang, Y. Emre, and C. Chakrabarti, Product code schemes for error correction in MLC NAND flash memories, IEEE Trans. VLSI Systems, accepted for publication. [2] C. Yi and J. H Lee, Interleaving and decoding scheme for a product code for a mobile data communication, IEEE Trans. Comm., vol. 45, no. 2, pp. 144-147, Feb. 1997 [3] B. Shin, S. Hong, H. Park, J. No, D. Shin, New Decoding Scheme for LDPC Codes Based on Simple Product Code Structure, [Online] http://arxiv.org/pdf/1203.4040.pdf [4] J. Hagenauer, E. Offer, and L. Papke, "Iterative decoding of binary block and convolutional codes," IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 429-445, Mar. 1996. [5] R.Y. Shao, S. Lin, and M. P. C Fossorier, "Two decoding algorithms for tailbiting codes," IEEE Trans. Comm. vol. 51, no. 10, pp. 1658-1665, Oct. 2003 [6] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam, The Netherlands: NorthHolland, 1978. [7] P. Elias, "Error-free coding," IRE Trans. Inform. Theory, vol. IT-4, pp. 29-37, Sep. 1954. [8] R. V. Cox and C. E. W. Sundberg, "An efficient adaptive circular Viterbi algorithm for decoding generalized tailbiting convolutional codes," IEEE Trans. Veh. Technol., vol. 43, no. 11, pp. 57-68, Feb. 1994. [9] H. H. Ma and J. K. Wolf, "On tail biting convolutional codes," IEEE Trans. Comm., vol. 34, no. 2, pp. 104-111, Feb. 1986. [10] Y. Yasuda, K. Kashiki, and Y. Hirata, "High-rate punctured convolutional codes for soft decision Viterbi decoding," IEEE Trans. Comm., vol. 32, no. 3, pp. 315-319, Mar. 1984. [11] T. Richardson and R. Urbanke, "The capacity of low-density parity-check codes under message-passing decoding," IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 599 618, Feb. 2001. [12] R. Johannesson and K. S. Zigangirov, Fundamentals of Convolutional Coding. NJ: IEEE Press, 1999. [13] S. Lin and D. J. Costello, Jr., Error Control Coding, 2nd Ed. NJ: Prentice Hall, 2004. 양필웅 (Pilwoong Yang) 2010년 2월포항공과대학교전자전기공학과공학사 2012년 2월서울대학교전기 컴퓨터공학부공학석사 2012년 3월~현재서울대학교전기 컴퓨터공학부박사과정 < 관심분야 > LDPC 부호, 오류정정부호, 통신시스템 520
논문 / 길쌈부호를수평부호로가지는곱부호의복호를위한유한연판정데이터결합 박호성 (Hosung Park) 2007년 2월서울대학교전기공학부공학사 2009년 2월서울대학교전기 컴퓨터공학부공학석사 2009년 3월~현재서울대학교전기 컴퓨터공학부박사과정 < 관심분야 > 압축센싱, LDPC 부호, 통신시스템홍석범 (Seokbeom Hong) 2007년 2월서울대학교전기공학부공학사 2009년 2월서울대학교전기 컴퓨터공학부공학석사 2009년 3월~현재서울대학교전기 컴퓨터공학부박사과정 < 관심분야 > 네트워크코딩, 압축센싱, 오류정정부호전보환 (Bohwan Jun) 2011년 2월서울대학교전기공학부공학사 2011년 3월~현재서울대학교전기 컴퓨터공학부석사과정 < 관심분야 > LDPC 부호, 오류정정부호, 통신시스템 노종선 (Jong-Seon No) 1981년 2월서울대학교전자공학과공학사 1984년 2월서울대학교대학원전자공학과공학석사 1988년 5월 University of Southern California 전기공학과공학박사 1988년 2월~1990년 7월 Hughes Network Systems, Senior MTS 1990년 9월~1999년 7월건국대학교전자공학과부교수 1999년 8월~현재서울대학교전기 컴퓨터공학부교수 < 관심분야 > 시퀀스, 협력통신, 시공간부호, 네트워크코딩, LDPC 부호, OFDM, 이동통신, 암호학신동준 (Dong-Joon Shin) 1990년 2월서울대학교전자공학과공학사 1991년 12월 Northwestern University, 전기공학과공학석사 1988년 12월 University of Southern California 전기공학과공학박사 1999년 1월~1999년 4월 Research Associate (USC) 1999년 4월~2000년 8월 Hughes Network Systems, MTS 2000년 9월~현재한양대학교전자통신컴퓨터공학부부교수 < 관심분야 > 디지털통신, 이산수학, 시퀀스, 오류정정부호, 암호학 521