DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

수미 함
5 years ago
Views:

1 논문 한국통신학회논문지 '09-05 Vol. 34 No. 5 높은무게 LDPC 부호의저복잡도고성능복호알고리즘 정회원조준호 *, 성원용 * High-Performance and Low-Complexity Decoding of High-Weight LDPC Codes Junho Cho*, Wonyong Sung* Regular Members 요 약 Low-density parity-check (LDPC) 부호의복호에는성능이좋은합곱알고리즘 (sum-product algorithm; SPA) 과하드웨어가간단한비트반전 (bit-flipping; BF) 알고리즘이많이쓰이고있다. 본논문은이들두가지방법의장점을가지는저복잡도고성능복호알고리즘을제안한다. 본제안된유연비트반전 (soft bit-flipping) 알고리즘은비트와체크노드사이에전달되는메시지를계산하는데단순한비교와덧셈연산만을필요로하며연산량이적다는장점이있다. 또한연산이완료된메시지의활용률을높이고비균등양자화 (non-uniform quantization) 를채용하여 1000 내외의부호길이에서 SPA 에 0.4dB 근접하는신호대잡음비 (signal-to-noise ratio) 를달성하였다. 본논문에서제안된알고리즘을이용하면, 행무게 (row weight) 와열무게 (column weight) 가높아서종래의 SPA 로구현하기어려웠던부호를비교적좋은오율성능을유지하면서실용적으로구현할수있다. Key Words : LDPC codes, Decoding, Low complexity, Soft bit-flipping, Sum-product. ABSTRACT A high-performance low-complexity decoding algorithm for LDPC codes is proposed in this paper, which has the advantages of both bit-flipping (BF) algorithm and sum-product algorithm (SPA). The proposed soft bit-flipping algorithm requires only simple comparison and addition operations for computing the messages between bit and check nodes, and the amount of those operations is also small. By increasing the utilization ratio of the computed messages and by adopting nonuniform quantization, the signal-to-noise ratio (SNR) gap to the SPA is reduced to 0.4dB at the frame error rate of 10-4 with only 5-bit assignment for quantization. LDPC codes with high column or row weights, which are not suitable for the SPA decoding due to the complexity, can be practically implemented without much worsening the error performance Ⅰ. 서론 1960년대초 Gallager에의하여고안된 low-density parity-check(ldpc) 부호 [1] 는 MacKay 등에의하여채널용량에근접하는우수한복호성능을보임이밝혀짐에따라 [2] 최근오류정정부호의분야에서중요한연구주제로부각되었다. 전통적인 LDPC 부호의복 호방식을신호의검출방법에따라크게두가지로분류하면, 0이나 1로엄격하게결정 (hard-decision) 된신호에대하여복호를시도하는비트반전 (bit-flipping; BF) 방식과실수 (real number) 범위에서다단계의값을가지는 (soft-decision) 신호에대하여복호를시도하는합곱알고리즘 (sum-product algorithm; SPA) 으로나눌수있다. BF 알고리즘은비트노드와체크노드를 본연구는교육과학기술부의 BK21 사업, 그리고하이닉스반도체주식회사의지원으로수행되었습니다. * 서울대학교전기컴퓨터공학부멀티미디어시스템연구실 (juno@dsp.snu.ac.kr, wysung@snu.ac.kr) 논문번호 :KICS , 접수일자 :2008 년 12 월 7 일, 최종논문접수일자 :2009 년 4 월 13 일 498

2 논문 / 높은무게 LDPC 부호의저복잡도고성능복호알고리즘 갱신 (update) 하는방식이매우간단하고두노드사이에교환되는메시지의크기가 1 비트에불과하기때문에구현이매우쉽지만에러정정성능이 SPA 에비하여크게뒤떨어진다. 반면 SPA 는일반적으로 LDPC 부호의복호알고리즘가운데가장우수한오류정정성능을보이는것으로알려져있으나체크노드업데이트에쌍곡선삼각함수 (hyperbolic trigonometric function) 를이용해야하며이상적인메시지는무한대의정밀도를가져야하기때문에구현의복잡도가지나치게높다는단점이있다. 이에따라오류정정성능을크게저하시키지않으면서도구현상의복잡도를줄이기위하여다양한연구가지속적으로수행되고있다. BF 알고리즘의성능을개선하는시도로서가중치비트반전 (weighted bit-flipping; WBF) 알고리즘등 [3]-[5] 이제안되었고, 다른한편으로 SPA의복잡도를줄이기위하여최소값합 (min-sum; MS) 알고리즘등 [6]-[7] 에대한연구도수행되었다. 지금까지의연구결과를보면, 이상적인 SPA 에필적하는높은에러정정성능을얻을수있었던알고리즘들은기본적으로신뢰전파 (belief propagation) 를위한외부 (extrinsic) 메시지를연산할때메시지를전달받을노드로부터오는메시지를제외하고나머지유입되는 (incoming) 모든메시지들에합이나곱의연산을수행하기때문에패리티행렬의열무게 (column weight) 와행무게 (row weight) 의제곱에비례하는 의연산복잡도를요구하고있다 [9]. 따라서구현에관한모든문헌은전체유입메시지의합과곱을먼저계산하고나중에전달대상노드로부터의메시지를제외하는방식의연산량최적화를통하여 의선형적인연산복잡도를달성하는구현방법을사용하고있다 [9]. 그러나이러한최적화를위해서는 SPA에서는추가적으로나눗셈기나뺄셈기가필요하며 [8], MS 알고리즘에서는두개의최소값을빠른시간안에찾는하드웨어의구현이쉽지않고저장공간도추가로필요하다는단점이있다 [9]. 이러한까닭으로기존의 SPA 또는 MS 방식의 LDPC 복호는 3이나 6 정도의매우낮은열무게또는행무게를가지는경우로실시간구현이제한이되어왔다. 본논문에서는 SPA 와 BF 알고리즘의장점을고루반영하여유연한비트반전 (soft bit-flipping; SBF) 을이용한 LDPC 의복호알고리즘을제안하고자한다. 제안된알고리즘은외부메시지로부터전달되는정보를내부 (intrinsic) 메시지에유연하게결합하여이후의반복복호 (iterative decoding) 과정 에서계속해서이용함으로써성능을높이는 SPA 의장점을가지고있다. 또한비트노드와체크노드에서상대편노드로전달하는메시지가단일하기때문에패리티행렬의행무게와열무게에선형적으로비례하는 의연산복잡도를갖는 BF 알고리즘의장점도가지고있다. 본논문은다음과같은순서로 SBF 알고리즘을제안하고그성능을검증하고자한다. 제 II장은 WBF 알고리즘과 improved modified WBF (IMWBF) 알고리즘에대하여소개한다. 그리고이를더욱개선하기위하여본논문에서제안하는 SBF 알고리즘을제 III 장에서설명한다. 제 IV장에서는다양한 LDPC 복호알고리즘의성능실험결과를비교하고, 제 V장에서결론을제시한다. Ⅱ. WBF와 IMWBF 알고리즘 Gallager에의해제안된 BF 알고리즘은패리티체크방정식에모두동일한가중치를부여했지만, 이를개선한 WBF 알고리즘 [3] 은각체크에관여되는비트가운데신호의크기가가장작은것을방정식의가중치로부여함으로써패리티체크방정식의신뢰성을차등화하는방법을사용하였다. WBF 알고리즘을개선한 IMWBF 알고리즘 [5] 은 WBF와마찬가지로체크방정식에가중치를부여하여복호를수행하지만가중치의값을결정하는방법이다르다. 다시말해 WBF 는각체크에연결된비트의정보를모두이용하는반면에, IMWBF는자기자신으로부터제공된정보를제거한후에메시지를전달받는것이다. IMWBF 알고리즘을소개하기위하여먼저 M 행 N열의패리티체크행렬 에의하여정의된 (d v, d c) 규칙 LDPC 부호를가정하자. 신호는 AWGN(additive white Gaussian noise) 채널에서 BPSK(binary phase-shift keying) 변조를이용하여전송하며, 부호어 은 의규칙에의하여이진벡터 으로변환된다고하자. 만약채널에평균이 0이고분산이 N 0/2인백색가우시안잡음 (white Gaussian noise) v n 이존재한다면수신된신호 은 로표현할수있다. 이때 m번째체크에관여하는비트의집합을 이라하고 n 번째비트에관여하는체크의집합을 이라하자. 그러면엄격결정벡터 499

3 한국통신학회논문지 '09-05 Vol. 34 No. 5 (hard-decision vector) 의값은 y n 이양수이면 z n=1, 음수이면 z n=0으로정해지며, 신드롬 는다음의식 (1) 에의하여정의된체크로부터구할수있다. s m = n B(m) z n h m,n. (1) 또한 IMWBF 알고리즘에서 n번째비트로부터 m번째체크로전달되는메시지의가중치 은다음과같이정의된다. \ (2) 관여된비트의최소값으로체크에부여되는가중치를결정하는것은, 이상적인 SPA 에서 tanh(hyperbolic tangent) 법칙에의해정의되는체크의 LLR(loglikelihood ratio) 값이비트의최소값으로근사화된다는사실에기인한다 [6]. 위에서설명한가정과정의를기반으로하여, IMWBF 알고리즘은다음순서에따라복호를수행한다. 초기화 : 반복회수 k 를 0으로초기화하고최대반복회수 를설정한다. 수신된신호로부터 n [1, N], m [1, M] 에대하여가중치 w n m 를모두구한다. 1단계 : 신드롬벡터 를계산한다. 만약 가영벡터이면 를부호어로출력하고복호를성공적으로종료한다. 2단계 : 모든비트에대하여다음과같이정의된반전함수 (flipping function) 를계산한다. e k n= m A(n) (2s k m-1)w n m -α y n. 3단계 : 다음의비트 n* 를반전함으로써엄격결정벡터 을갱신한다. n*=argmax n [1,N] e k. n 4단계 : 반복회수 k 를 k+1 로증가시키고 1단계로돌아간다. 만약 가되어반복회수제한을넘으면복호실패를선언하고복호를종료한다. 여기서복호과정 2단계의가중치인수 는신호대잡음비 (signal-to-noise ratio; SNR) 에따라다른최적값을갖는양의실수이다. Ⅲ. SBF 알고리즘의제안 IMWBF 알고리즘은 WBF의체크연산과정에 SPA의방법론을적용함으로써성능향상을도모하고있지만몇가지한계를가지고있다. 첫번째는복호의반복과정전반에걸쳐서수신된벡터 y가그대로유지되고단지엄격결정벡터 z만이매번갱신된다는점이다. 따라서복호반복도중에각비트가외부로부터새로얻게되는정보가매우제한적이며최초에내부에가지고있던정보가지배적인영향을계속유지하게된다. 두번째로, 한번의복호반복에서는가장큰반전함수값을갖는한개나소수개의엄격결정비트만이반전될뿐이고나머지비트들은어떠한영향도받지않는다는점이다. 체크연산에의해이미알게된추가정보의상당부분이그대로낭비되는셈이다. 세번째로 Gallager의 BF 알고리즘이가지고있던장점인, 작은저장공간과간단한연산이라는성질을상당부분잃게되어, 강력한복호성능을보이면서도구현이상당히용이한 MS 알고리즘에대한비교우위가불확실하다. 이러한단점들을극복하기위하여본논문이제안하는복호알고리즘은다음과같다. 먼저각패리티체크방정식에부여되는가중치는, 그에관여되는비트의최소값이아니라비트의총합으로서결정된다. 즉 m번째체크에부여되는가중치는다음식 (3) 과같이정의된다. (3) 이것은, SPA 에주로쓰이는 LLR 을사용하지않고 LD(likelihood difference) 를사용하면비트로부터오는메시지의곱에의해체크의값을계산할수있다는데에이론적근거를두고있다 [7]. LD로부터식 (3) 을유도하는더욱자세한과정은본논문의부록에수록되어있다. 식 (3) 과같이변경된가중치를이용하면, Gallager의 BF 알고리즘처럼체크하나는한종류의메시지만보내기때문에복잡도가낮아진다. 예를들어행무게와열무게가모두 33인부호를사용한다면 SPA나 IMWBF를최적화없이바로구현하기위해서는비트와체크노드당 32( 연산 / 메시지 ) 33( 메시지 / 노드 )=1056( 연산 / 노드 ) 회의연산이필요하지만, SBF에서는노드당 32회의연산이필요할뿐이다. 이경우기존의 MS 알고리즘에서는트리 (tree) 구조로최소값두개를찾는방식으로노드당연산수를 37 회로줄일수있지만 [9], 트리구조를탐색 (traverse) 하 500

4 논문 / 높은무게 LDPC 부호의저복잡도고성능복호알고리즘 는하드웨어의구현이어렵고체크노드한개에최소값두개가저장되어야하기때문에체크노드를위한저장공간이 SBF보다두배소요된다. 한편, SBF의반전함수는 IMWBF와동일한것을사용하지만, 반전함수의계산결과를이용하여수신벡터의신뢰도를향상시키는방법은차이가있다. 즉, 가장큰반전함수값을가지는엄격결정비트만이반전되는방식이아니고, 반전함수값을미리정의된순차적인크기의여러임계값과비교하여 y i 자체를변경하는방식이다. 이때, 반전함수가크면클수록 y i 가반대편신호방향으로이동되는정도가크도록한다. 반대로반전함수가매우작다면 y i 는자신의신호크기를강화하는방향으로갱신된다. 이처럼반전함수가수신신호의갱신에반영되는정도가비례적이기때문에, 즉유연하기때문에본알고리즘을 유연한비트반전 (soft bit-flipping) 알고리즘 이라지칭하기로한다. 유연한비트반전방식은 IMWBF가가지는두가지단점, 즉비트노드반전결과가다음체크값계산에불완전하게전파되고상당부분단절된다는점과반전함수가제공하는정보가비트반전과정에서극소량반영되고대부분손실된다는점을동시에극복할수있다. SBF 의동작원리는 SPA 가외부정보를이용하여수신신호의신뢰도를반복적으로높여나가는것과근본적으로일맥상통한다. SBF 알고리즘을실제회로로구현할때, 수신된신호와비트노드, 체크노드에저장되는신호를모두 q 비트로양자화하는상황을가정하자. 이때비트노드와체크노드는 2 q -1개의임계값 과 를경 계로하여 ±0 을제외한부호- 크기 (sign-magnitude) 의방식으로각각양자화되며, 비트반전의강도는임계값 에의해정해진다고하자. 그러면 SBF 알고리즘은다음순서에따라복호를수행한다. 초기화 : 반복회수 를 0으로초기화하고최대반복회수 를설정한다. 1단계 : 신드롬벡터 를계산한다. 만약 가영벡터이면 를부호어로출력하고복호를성공적으로종료한다. 2단계 : 경계값 에따라 을 비트로양자화한후, 식 (3) 에의해정의된체크노드 의가중 치 를계산하고 를경계로하여양자화한다. 3단계 : 모든비트에대하여다음과같이정의된 반전함수를계산한다.. 4단계 : 반전함수에따라각비트노드에다음과같이유연한반전을수행한다. i) 일때 ( 비트의강한반전 ), ii) 일때 ( 비트의약한반전 ), iii) 일때 ( 비트의유지 ), iv) 일때, ( 비트의강화 ). 어떤비트노드에서도반전이일어나지않는다면, 로조정한다. 5단계 : 반복회수 를 로증가시키고 1단계로돌아간다. 만약 가되어반복회수제한을넘으면복호실패를선언하고복호를종료한다. 여기서복호과정 4단계의임계값조정상수 는 q에따라다른최적값을갖는양의정수이다. Ⅳ. 모의실험결과본논문에서는유한체 (finite field) 위의사영기하학 (projective geometry; PG) 에존재하는점과선, 면에의하여생성되는 PG-LDPC 부호 [3] 를이용하여 SBF의성능을검증하였다. PG-LDPC 부호는생성과정에서본질적으로주기성을내포하게된다. PG-LDPC 부호는패리티행렬의행무게와열무게가큰단점이있지만비슷한길이와부호율을갖는 LDPC 부호가운데가장좋은오류정정성능을보이는것으로알려져있다. 특히 BF 알고리즘과 WBF 알고리즘에서 Gallager 501

한국통신학회논문지 '09-05 Vol. 34 No. 5 Frame Error Rate 10 0 10-1 10-2 10-3 SPA WBF IMWBF 10-4 BF SBF 1bit SBF 2bit SBF 3bit 10-5 SBF 4bit SBF 5bit SBF 6bit 10-6 2 2.5 3 3.5 4 4.5 5 5.

5 한국통신학회논문지 '09-05 Vol. 34 No. 5 Frame Error Rate SPA WBF IMWBF 10-4 BF SBF 1bit SBF 2bit SBF 3bit 10-5 SBF 4bit SBF 5bit SBF 6bit E b /N 0 (db) Average Number of Iterations until Decoding Success SPA BF SBF 1bit SBF 2bit SBF 3bit SBF 4bit SBF 5bit E b /N 0 (db) 그림 1. 부호율 0.77 인 (1057, 813) PG-LDPC 부호의블록오율성능 (Block error rate of rate 0.77 (1057, 813) PG-LDPC code) 부호보다월등한성능을보이는데, 두알고리즘에서는행과열의무게가구현의복잡도에중대한영향을미치지않기때문에, 주기성을갖는특성과더불어구현이용이하면서도복호성능이매우뛰어난부호이다. 그림 1은부호율이 0.77이고행무게와열무게가모두 33인 (1057, 813) PG-LDPC 부호의블록오율 (frame error rate; FER) 성능을보여준다. 그래프에서 WBF와 IMWBF 알고리즘, 3~6비트 SBF 알고리즘은복호의최대반복회수를 200회로제한하였고 SPA와 1~2비트 SBF 알고리즘은 50회로제한하였다. SBF 는양자화에할당된비트수를 1비트에서 6비트까지변화시키며오율을측정하였고, 다른복호알고리즘들은부동소수점 (floating point) 을이용한결과이다. SBF의양자화에할당된비트수를점차늘릴때 2비트이하에서는 SBF가 WBF 보다좋지않은성능을보이나, 불과 3비트만으로도부동소수점의 WBF를능가하는성능을보이기시작한다. 5비트에도달하면 IMWBF 보다좋은성능을보이고, 10-4 의블록오율에서 SPA 에약 0.4dB 정도까지근접하는성능을나타낸다. 비트수를증가시켜도지속적으로성능향상이이루어지고있으나 4비트이상에서는다소향상의정도가줄어든다. 다음은 SBF 의복호속도에대한분석이다. 복호가성공할때까지필요한평균반복회수를 라하자. 최대반복회수를 라하고블록에러율을 라하면, 복호의성공과실패를모두포함하여소요되는총소요시간의기대값은 로계산할수있다. 따라서복호에소요되는시간은복호의성공률과복호수렴속도에동시에영향을받는다. SBF 알고리즘을이용하여 (1057, 813) PG-LDPC 부 그림 2. (1057, 813) PG-LDPC 부호의복호성공까지필요한평균반복회수 (Average number of iterations until decoding success of (1057, 813) PG-LDPC code) 호를복호할때복호가성공할때까지소요되는반복회수 ( ) 를그림 2에도시하였다. 그림에서볼수있듯이 SBF 알고리즘은 BF 알고리즘이나 SPA 에비하여복호수렴속도가훨씬느리며, 할당된비트수가늘어날수록더욱더느려진다. 이것은 SBF 복호중비트반전단계 ( 제 4단계 ) 에서양자화비트수에따라비트의동적영역 (dynamic range) 이 으로지수적으로증가하는반면에비트반전의강도는 1 이나 2 정도로유지되기때문이다. 즉 SBF 알고리즘은비트가포함하고있는정보를보수적으로변화시킴으로써, 에러일가능성이매우높은비트부터반전하기시작하여복호반복이진행되면서순차적으로반전하는방식으로복호의성공률을높이는것이다. 복호수렴시간이길다는단점은문헌 [3] 에서제시한방법과유사하게 BF와 SBF를모두이용하는 2 단계 표 1. 오율성능실험에사용한임계값 (Threshold values used in the error performance simulation) 502

6 논문 / 높은무게 LDPC 부호의저복잡도고성능복호알고리즘 혼성복호 (2-stage hybrid decoding) 를통하여극복이가능하다. 즉, 수렴속도가매우빠른 BF 알고리즘으로최대 5회이하의반복회수를부여하여먼저복호를시도한후에실패하는경우에만느리지만복호성공률이높은 SBF 알고리즘으로 2차복호를시도하는방식이다. BF와 SBF 두가지알고리즘은매우비슷한구조로동작하기때문에복호회로를공유하면서약간의추가제어신호만을이용하여복호시간을단축시킬수있을것으로예측된다. 표 1에는양자화비트가 2~4인경우의성능모의실험에사용한여러가지임계값을정리하였다. 표에서보는바와같이 SBF 알고리즘에는 개의파라미터가필요하기때문에비트수가늘어나면필요한파라미터의수가많아진다. 이가운데하나의파라미터를변경하면다른파라미터들이영향을받기때문에여러파라미터의최적조합을찾는것은시간을요하는일이다. 파라미터값을결정하기위해서는먼저 SBF의복호과정에서비트와체크노드가어떤분포를갖는가를알아야하고, 파라미터의이동으로인하여그분포가어떻게변화되는가를알아야한다. 그러나통계적으로조사된비트와체크의분포에 Lloyd-Max의양자화방법을적용하여구한임계값이실험결과좋은복호성능을보이지는않았는데, 이것은일반적인양자화의효율성이필연적으로복호성능의향상을가져오지는않기때문으로보인다. 본논문에서는부록에유도된바와같이 LD의양자화를위하여지수함수 를쓰는대신에, 양의구간에서 가증가할수록지수함수처럼기울기가증가하면서도 가 1에접근할수록함수값이무한대로발산하는역오류함수 (inverted error function) 를사용하였 다. 여기서오류함수는 로 정의된다. 지수함수 가밑 를어떤값으로선택하더라도 가충분히작은음의정수가되면 와 사이의구간이너무좁아져서양자화효율이떨어지는단점이있는반면에, 역오류함수는 x축에정의된구간이 로한정되어있기때문에양자화비트수가늘어나서 x축을따라많은구간으로양자화가되어도양자화효율이크게줄어들지않는다. 목적함수 (objective function) 를오율성능으로두고모의담금질 (simulated annealing) 을통하여파라미터의최적조합을찾는방법도있겠지만이또한너무많은시간을필요로하여실용성이없었다. 따라서 SBF 알고리즘에사용되는비균등양자화의양자화구간을효율적으로설정하는분석적인 (analytic) 방법이연구된다면장시간의모의실험을하지않고도좋은오율성능에도달할수있을것이다. Ⅴ. 결론 본논문에서는오율 (error rate) 성능이좋으면서도하드웨어복잡도가낮은 SBF (soft bit-flipping) 알고리즘을제안하였다. SBF 알고리즘을이용하면비트와체크노드가상대노드에보내는메시지가단일하고메시지연산이간단하기때문에 PG-LDPC 부호와같이행무게와열무게가높은부호라도충분히실용적으로구현할수있다. 이와동시에노드간상호전달메시지의이용효율을높임으로써 BF 알고리즘에비하여 SPA 에상당히근접한오율성능을보임이 PG-LDPC 부호를통하여검증되었다. 그러나 SBF 알고리즘은메시지의비균등양자화 (non-uniform quantization) 에필요한여러가지양자화임계값들을찾는방법이명확하게밝혀지지않았기때문에높은오율성능을얻기위해서는최적임계값을많은모의실험을통해구하는것이필요하다. 비균등양자화가회로구현에미치는영향도분석될필요가있다. 또한부호의길이가 1057 인 PG-LDPC 부호에대해서만성능검증이이루어졌기때문에차후다양한부호에대한추가의실험을통하여일반적인성능의검증이필요하다. 부록 SBF 알고리즘의가중치유도 비트노드 p가 0 과 1일확률을각각, 이라하자. 이때노드 p의 LD는 로정의된다. 이때노드 p와 q를포함한 3개의비트노드와연결된체크노드가 p와 q로부터나머지하나의비트노드로전파하는 LD 값은다음과같이유도할수있다. (4) 한편, 이므로, 를 q 비트로양자화할때임 의의실수 정수 에대하 여 를 의양자화대표값 503

한국통신학회논문지 '09-05 Vol. 34 No. 5 (representation level) 으로정할수있다. 따라서두비트노드의양자화된 LD, 로부터계산되는체크노드의값은다음과같다. (5) 비트노드와체크노드에지수적인방식으로양자화된 LD의밑 를미리정의해둔다면비트노드 p와 q는 LD의부호, 와, 양의방향으로 평행이동시킨지수의값, 만전송하면된다.

Theory, vol. IT-8, pp. 21-28, Jan. 1962.7 [2] D. J. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399-432, Mar. 1999. [3] Y. Kou, S.

7 한국통신학회논문지 '09-05 Vol. 34 No. 5 (representation level) 으로정할수있다. 따라서두비트노드의양자화된 LD, 로부터계산되는체크노드의값은다음과같다. (5) 비트노드와체크노드에지수적인방식으로양자화된 LD의밑 를미리정의해둔다면비트노드 p와 q는 LD의부호, 와, 양의방향으로 평행이동시킨지수의값, 만전송하면된다. 따라서 일때 는 에 대하여단조증가함수이므로 로근사화할수있다. 즉, 체크노드의신뢰도는다음과같이근사화될수있다. (6) 여기서지수함수를선형함수로근사화할때발생하는오차는체크노드의비균등양자화를통하여감소시킬수있다. 참고문헌 [1] R. G. Gallager, Low-density parity-check codes, IRE Trans. Inform. Theory, vol. IT-8, pp , Jan [2] D. J. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inf. Theory, vol. 45, no. 2, pp , Mar [3] Y. Kou, S. Lin, and M. P. C. Fossorier, Low-density parity-check codes based on finite geometries: A rediscovery and new results, IEEE Trans. Inf. Theory, vol. 47, no. 7, pp , Nov [4] J. Zhang and M. P. C. Fossorier, A modified weighted bit-flipping decoding of low-density parity-check codes, IEEE Commun. Lett., vol. 8, no. 3, pp , Mar [5] M. Jiang, C. Zhao, Z. Shi, and Y. Chen, An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes, IEEE Commun. Lett., vol. 9, no. 9, pp , Sep [6] M. P. C. Fossorier, M. Mihaljevic, and H. Imai, Reduced complexity iterative decoding of low-density parity check codes based on belief propagation, IEEE Trans. Commun., vol. 47, no. 5, pp , May [7] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, Factor graphs and the sum-product algorithm, IEEE Trans. Inf. Theory, vol. 47, no. 2, pp , Feb [8] A. Darabiha, A. C. Carusone, F. R. Kschischang, Block-interlaced LDPC decoders with reduced interconnect complexity, IEEE Trans. Circuits and Systems II, vol. 55, no. 1, pp , Jan [9] J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X-Y. Hu, Reduced-complexity decoding of LDPC codes, IEEE Trans. Commun, vol. 53, no. 8, pp , Aug 조준호 (Junho Cho) 정회원 2004년 2월서울대학교전기공학부졸업 2006년 2월서울대학교전기컴퓨터공학부석사 2006년 3월 ~ 현재서울대학교전기컴퓨터공학부박사과정 < 관심분야 > 오류정정부호, 알고리즘설계및구현성원용 (Wonyong Sung) 정회원 1978년 2월서울대학교전자공학과졸업 1980년 2월한국과학기술원전기전자공학과석사 1987년 6월미국 University of California, Santa Barbara (UCSB) Electrical and Computer Engineering Department 박사 1989년 2월 ~ 현재서울대학교전기컴퓨터공학부교수 504

Sequences with Low Correlation

Sequences with Low Correlation 레일리페이딩채널에서의 DPC 부호의성능분석 * 김준성, * 신민호, * 송홍엽 00 년 7 월 1 일 * 연세대학교전기전자공학과부호및정보이론연구실 발표순서 서론 복호화방법 R-BP 알고리즘 UMP-BP 알고리즘 Normalied-BP 알고리즘 무상관레일리페이딩채널에서의표준화인수 모의실험결과및고찰 결론 Codig ad Iformatio Theory ab /15