채널코딩 -- 발전과정과 현재 상황 -- 디지털 통신 시스템을 중심으로

Size: px

Start display at page:

Download "채널코딩 -- 발전과정과 현재 상황 -- 디지털 통신 시스템을 중심으로"

혜은 유
6 years ago
Views:

1 lecture # 오류정정부호 24 년 2 학기 연세대학교전기전자공학과 송홍엽교수

2 Contents 채널코딩의역사 과목소개

3 채널코딩의역사 -- 발전과정과현재상황 -- 디지털통신시스템 송홍엽 Coding and Crypto Lab 연세대학교전기전자공학부

4 Based on the content of the following address: History and Current Status of Channel Coding 채널코딩의발전과정과현재상황에대한요약 Professor, School of Electrical and Electronic Engineering Yonsei University December 29 Hong-Yeop Song 29 "No part of this document can be reproduced, reposted, and recaptured without permission from the author, except for the personal use."

5 초당백만비트를 ( 오류없이 ) 송수신가능할까?? 이는대략적으로오늘날디지털핸드폰의전송속도다. 하루에 비트를전송하는 ( bit/day) 통신시스템은대충허접하게적당히만들어도무오류송수신이가능하게만들수있다. 초당백만비트속도는간단히계산해보아도, Mbit/sec = 3,6*24*,, bit/day = 86.4 Giga bit/day = 86,4,, bit/day

6 INFORMATION THEORY TELLS US...

7 I. Introduction - Digital Communication System Crypto Encoder Channel Encoder waveform Crypto Decoder Channel Decoder SOURCE Coding Channel Crypto Coding Channel

8 Shannon s Noisy Coding Theorem

9 Multiple-Access Channel (Broadcasting Channel) (FDMA/TDMA/CDMA/OFDMA ) BS Multiple MS in the coverage Multi-Input Multi-Output (MIMO) Channel Encoding Modulation Mapping H Demapping Demodulation Decoding

10 Other Channels Wired Channels Computer Communication/Internet Coaxial cable, DATA MODEM LINE, Optical Cable, etc Usually modeled as DMC-BEC Recoding Channels Magnetic Tapes Digital Memory Digital Camcorder/Hard Disk/Laser Disk Usually modeled as channel with MEMORY and Burst Errors Underwater Acoustic Channels for SONAR Propagation characteristics is much different

11 Conclusion of Shannon s Noisy Coding Theorem When the RATE decreases more and more, the RELIABILITY of communication over the noisy channel increases more and more. Conversely, do we have to reduce the RATE as small as possible (in order to increase RELIABILITY of communication over noisy channel)??? NO (by Shannon s Noisy Coding Theorem). There is a limit on the rate (capacity=max rate) under which a reliable communication is possible without further reducing the rate. Such possibility is proved by the proof of the existence of a channel code.

12 PART. FIRST 6 YEARS SINCE SHANNON (94~2) ALGEBRAIC BLOCK CODES CONVOLUTION CODES

13 II. Shannon (948) ~ 99 년대 이기간중의채널코딩연구의역사는크게두갈래로나뉜다. 대수학에근거한대수학적블럭코드가한갈래이고, 컴퓨터시믈레이션과유한상태기계이론에근거한컨벌루션코드가있다. 물론이두가지를연접하여당시로서는상상할수없는좋은효과를거두기도했으며, 미국 NASA/JPL 에서는태양계탐사위성에이를성공적으로사용하기도하였다. 우측사진은보이저 2 호의모습이다. 현재지구로부터약 2 억 Km 지점에서초속 2Km 의속도로멀어지고있다. 보이저 2 호에서보내는신호는빛의속도로약 2 시간을날아와지구에도달한다. 이러한통신시스템에서는채널코딩이신뢰도에결정적인역할을한다. 여기에는컨벌루션코드와 RS 코드의연접코드가사용되어우주의신비로운영상을생생한모습으로보낸다.

14 II. 대수학적블럭코드의발전 이쪽분야의연구자들은대수학적블럭코드를잘발전시키면반드시 Shannon 이예측한우수한성능의채널코드를찾을수있으리라굳게믿고많은노력을기울였다. Hamming 코드, Golay 코드, Hadamard 코드, Reed-Müller 코드, BCH 코드, Reed-Solomon 코드로이어지는발전은실로놀랍다. Hamming 박사는 ( 통신시스템이나 Shannon 의이론과관계없이 ) 컴퓨터시스템의입출력에존재하는 비트의오류를스스로정정하는이진코드를만들었다.

15 Binary Hamming Code Binary linear Hamming code with parameter r 2 has a parity check matrix whose columns are all the non-zero binary r-tuples. Some parity check matrices are: for r=2, for r=3, for r=4 H H H Richard Hamming

16 Patterns for any r 2 (by Dr. Hamming) Case r = 2 Case r = 3 Case r =

17 이후의발전과정을보면, 선형대수학의벡터공간의개념이주로사용되었다. 7~8 년대들어 RS 코드를일반화하는과정에서대수기하학의이론을사용하기시작했다. 실로수학분야에서조차그들만의수학이라는대수기하학의핵심적인내용을사용하는기법들이속속발표되었지만, 코드의구조만매우복잡해졌을뿐, 채널코드의성능면에서는 RS 코드에비하여그리괄목할만한큰성장을이루지는못하였다.

18 RS 코드는 7 년대이후우리가접하는거의대부분의디지털기기에사용되어디지털시대를활짝여는주요기술이된것만은사실이다. 디지털음악 CD 의음악저장방식과 MP3 의음악파일처리기법등에핵심적으로사용되며, 디지털방송기법에는지금도 RS 코드가주요하게사용된다. 또한 RS 코드는컨벌루션코드와연접되어태양계탐사위성에성공적으로적용되기도하였다. 여기까지가대수학적블럭코드의한계인듯보였다. 대수학적블럭코드는나중에 LDPC 코드의출현으로완전히새로운상황을맞이하게된다.

BCH 코드의특별한형태임이증명된 RS 코드의디코딩방식개발에는재미있는일화가있다. 6 년대후반에 Berlekamp 박사는 BCH 코드의새로운디코딩방식의논문을 IEEE 정보이론학술지에제출하지만당시로서어느심사위원도이를이해하지못하여채택을거부당하게된다.

19 BCH 코드의특별한형태임이증명된 RS 코드의디코딩방식개발에는재미있는일화가있다. 6 년대후반에 Berlekamp 박사는 BCH 코드의새로운디코딩방식의논문을 IEEE 정보이론학술지에제출하지만당시로서어느심사위원도이를이해하지못하여채택을거부당하게된다. Berlekamp 박사는이에자신의논문의핵심적인내용과주변이론을정리하여한권의단행본으로출간하는데이저서의제목이 " 대수학적코딩이론 " 이다. 그후이책의내용에대한검증이이루어지고 IEEE 정보이론학회는해당학술지에지난 년간게재된논문중에선정하여수상하는 " 최우수논문상 수상자로 969 년에야 Berlekamp 박사를선정하는데, 수상작은바로이단행본이다.

그런데 Berlekamp 박사의디코딩이론의핵심적아이디어는놀랍게도이보다 6 여년전 2 세기초에잠시나타났다가요절한인도의천재수학자라마누잔의유고논문집에단 2 페이지의논문 " 연립방정식에대한소고 " 로부터얻었다는느낌이드는데, 이는라마누잔의논문에제시된비선형연립방정식의풀이법이정확하게

20 그런데 Berlekamp 박사의디코딩이론의핵심적아이디어는놀랍게도이보다 6 여년전 2 세기초에잠시나타났다가요절한인도의천재수학자라마누잔의유고논문집에단 2 페이지의논문 " 연립방정식에대한소고 " 로부터얻었다는느낌이드는데, 이는라마누잔의논문에제시된비선형연립방정식의풀이법이정확하게 Berlekamp-Massy 알고리즘의핵심을이루기때문이다. 우연의일치일까, 아니면아이디어를받아온걸까... G. H. Hardy and S. Ramanujan Berlekamp 박사는나의지도교수 Golomb 박사와개인적으로깊이있는친분관계를가지고있기때문에많은학회에서지금도마주치고있다.

21 (II.2) 컨벌루션코드의발전 Elias 와 Shannon 에의해서처음제안된트리코딩방식은디코딩방식의복잡도가매우높아서실용성을띄지못하다가, 그나마조금덜복잡한선형트리코드가주목을받기시작했다. 이를컨벌루션코드라부른다. 이코드는 6 년대 Viterbi 박사에의해서처음제안되었고 Forney 박사가최적이라고증명한디코딩방식 ( 비터비알고리즘 ) 이알려지면서현실적인통신시스템의실질적인표준으로자리잡게된다. Coding rate and constraint length Coding rate R = k/n : number of data bits per coded bit Constraint lengths K of the encoder: Encoder with K- memory Example: rate= ½, K=3, or (2,,3) Convolution Code + Connection g(x) = + X + X 2 u: First code symbol Input bits Output branch word u2: Second code symbol + Connection 2 g2(x) = + X 2

22 Viterbi 박사는 MIT 에서석사를마친뒤에 JPL 에서 Golomb 박사의수학적통신이론팀에서근무하게되는데, 당시 Caltech 으로부터파트타임박사과정입학에거절당하고, Golomb 박사의권유로 USC 에서박사과정을밟게된다. 이러한인연으로 Viterbi 박사는자신이설립하여 CDMA 기술로 2 세대무선이동통신을평정한 Qualcomm 사를은퇴하면서 Viterbi 재단을설립하고 USC 공과대학에막대한지원금 ( 약 52 Million USD) 을기부하여공과대학명칭을 USC School of Engineering 에서 USC Viterbi School of Engineering 으로바꾸어놓았다. Viterbi 박사 (biography) 는 USC 를졸업하고이후많은벤쳐기술회사를창업하여오다가 8 년대캘리포니아샌디에고에설립한 Qualcomm 회사에서디지털 CDMA 기술로이동전화표준을개발한이래전세계표준을주도하다가최근은퇴하였다. 나는 9 년대중반 Qualcomm 사에근무할당시 Viterbi 박사 [ 당시 CTO = Chief Technical Officer] 와몇차례기술적인회의를함께한기억이있을뿐더러지도교수와의절친한친분관계때문에지금도여러학회에서마주치곤한다.

23 이후 7 년대를지나면서 convolution code 는통신위성의통신시스템과수많은통신시스템의채널코딩기법으로사용되게되었고, 지금까지도 2 세대와 3 세대디지털이동전화기의핵심기술로사용되고있다. 즉, 여러분이지금손에서놓지못하고있는모든핸드폰의통신방식에사용되고있는것이다. 또한, 이후에출현할터보코드의기본구성으로중요한역할을하게된다.

24 Concatenated Coding Scheme for space channel DATA BITS RS Encoder and Interleaver SPACECRAFT Convolution Encoder TRANSMITTED CHANNEL SYMBOLS DECODED BITS RS Decoder and Deinterleaver GROUND Viterbi (Convolution) Decoder RECEIVED CHANNEL SYMBOLS Odenwalder (97) Concatenation scheme Inner code: convolution code Outer code: RS code with interleaver Great advantage on the space channel

25 Challenge of Channel Codes at P b = -5 Eb/No=.76dB bits/symbol Eb/No=9.6dB BW EFF MARINER MARS Mission 6/32=.875 bits/symbol Eb/No=6.4dB /2 bits/symbol Eb/No=5.7dB GALILEO Mission.25 bits/symbol Eb/No=.75dB [255,223] RS + (4,,4) CC with MLD PIONEER Mission.5 bits/symbol Eb/No=2.5dB (SL=dB) (2,,3) CC with SD VOYAGER Mission.5 bits/symbol Eb/No=2.5dB (SL=dB) [255,223] RS + (2,,6) CC with MLD

26 CCSDS Standard Consultative Committee for Space Data Systems 984 May: official recommendation for a telemetry channel coding standard Without concatenated system recommendation K=7, rate ½ code recommended Concatenated system recommendation Outer RS code: (255, 253) code over GF(2 8 ), interleaving depths of, 2, 3, 4, and 5 Bit-serial finite field arithmetic using dual basis

27 Shannon Limit 에접근하는코드는컨벌루션코드일까아니면대수학적블럭코드일까? 98 년대후반내가대학원에서공부하던시절, 주위의많은동료들이나교수들이이러한논쟁을자주했었다. 결론적으로 Shannon Limit 에근접하는코드는 ( 컨벌루션코드인가혹은대수학적블럭코드인가하는코드의모양에상관없이 ) 디코딩방식이무엇인가에의해서결정이되었다. 그디코딩방식은 ( 터보코드와 LDPC 코드에공통적으로사용되는 ) 확률적반복복호방식이다.

28 PART 2. NEXT 2 YEARS OR SO (99~2) TURBO CODES LDPC CODES

29 III. 993 년이후지금까지 993 년, 채널코딩분야에서는강력한지진이발생한것과비슷한결과를보게되었는데이는바로 Turbo 코드의출현이다. 이는놀랍게도지금까지위의많은채널코딩연구자들이아닌전자회로설계분야의전문가 Berrou 박사와 Glabieux 박사가공동으로채널코드를만들어실험해본결과를 IEEE 국제통신기술학회 (IEEE International Conference on Communications) 에논문으로발표하였는데, 우수한성능과속도를보여주는이결과앞에서지금까지몇십년간채널코드를연구해왔던많은연구자들은놀라움을금치못하게되었다. 터보코드는 Shannon 이예측한우수한채널코드에거의완벽하게근접한결과라는게대부분의관련연구자들의공통된의견이다. 이후 997 년에 IEEE 정보이론학회는이학술대회발표내용을저널지 IEEE Trans. Comm 에 96 년출간한동일제목의논문에자기네학회의 " 최우수논문상 " 을수여하게된다. 우리나라이었더라면표절문제가대두되었을까??

Turbo 코드는매우간단한두개의컨벌루션코드를병렬로연접한결과이고 디코딩방식은지금까지알려진그어떤방식과달리, 두개의디코더가서로의결과를주고받는작업을반복하는방식으로, 기계공학분야의터보엔진의동작특성과유사하다는이유로터보코드라고이름지었다고한다.

30 Turbo 코드는매우간단한두개의컨벌루션코드를병렬로연접한결과이고 디코딩방식은지금까지알려진그어떤방식과달리, 두개의디코더가서로의결과를주고받는작업을반복하는방식으로, 기계공학분야의터보엔진의동작특성과유사하다는이유로터보코드라고이름지었다고한다. [Encoder/Decoder] 이러한전혀새로운접근이 ( 매우간단하면서도 ) 어떻게그렇게놀라운성능을초래하는지에대하여그이후많은연구가이어졌고지금은그비밀이거의대부분밝혀진상태이다. 이는이제 3 세대에서 4 세대로넘어가는디지털이동전화기의표준방식으로제안 / 확정되었고 현재한국산이동인터넷의표준방식인와이브로기술에도핵심적으로사용되며, 4 세대전화기 (LTE) 에도표준방식으로사용되고있다.

31 Performance of Turbo Codes BER drops very rapidly once a critical value of E b /N has been reached Rate ½ over AWGN channels Uncoded Turbo coded Shannon Limit less than.5db B A The larger the size of interleaver the higher performance Large number of iteration decoder latency increase Question: where to go? A or B? (maybe case B: error-floor)

32 그런데놀라운사실이곧이어다시알려지게되었으니, 이는 Mackey 박사가재발견한 962 년도의논문의내용이고그제목은 LDPC 코드이며저자는 Gallager 박사이다. Robert Gallager LDPC 코드는컨벌루션코드를이용하는터보코드와달리대수학적블럭코드이다. 이는 62 년에 IEEE 정보이론학술지에 Gallager 박사에의해처음발표되었는데, 당시로선인코딩 / 디코딩의복잡도가상상을초월하기때문에 [ 그럴것이라고지금예측함 ] 아무도관심을보이지않은채, 약 3 여년간잊혀진상태였다.

33 LPDC 코드는대수학적블럭코드이지만이전의대수학적디코딩방식을사용하는게아니라터보코드의디코딩방식과개념적으로일치하는확률적반복복호방식을사용하고있다는점이놀라웁다. LDPC 코드는지금도많은관심을받고있으며, 세밀하게설계되면터보코드보다도더좋은성능을가진다는것이잘알려져있다. 단지인코딩 / 디코딩과정의복잡도가터보코드보다아직은훨씬더커서실용적으로적용되기위한많은연구가필요한상태이다. Many capacityapproaching LDPC codes Example (Chung 2) within.45db of the Shannon Limit

34 PART 3. RECENT YEARS OR SO (2~ 현재 ) FOUNTAIN CODES RAPTOR CODES POLAR CODES ETC...

35 IV. Fountain Code - LT code - Raptor code 이진대칭채널 (Binary Symmetric Channel) 로모델링되는일반통신채널은 과 이서로바뀌어수신되는오류때문에이를정정하는채널코딩기법이필수적이라하겠다. 인터넷이생활의필수품으로자리잡고있는오늘날인터넷유선채널은이진대칭채널이라기보다는이진소거채널 (Binary Erasure Channel) 로모델링하는편이훨씬더정확하다. 이는 과 을받으면이는확실한 ( 오류없는 ) 수신값이지만, 가끔씩 인지 인지판단할수없는수신값이나타나는채널이다. 이를소거값 (Erasure) 이라고부른다. 이는오늘날인터넷유선채널을효과적으로모델링한다. 이러한채널에서의채널코딩기법으로나타난채널코드를 fountain code 혹은 rateless code, erasure code 라고도부르며, 약 여년전 Luby 에의해서 Luby-Transform (LT) code 로정형화되었고, LT code 는다시무선채널을위하여스위스공과대학의 Shokrollahi 박사에의해서 Raptor code 라는이름으로 LDPC 코드와결합되었다. 놀랍게도이코드는오늘날인터넷뿐만아니라이동성이있는다양한무선네크워크상에서의응용성이뛰어나최근주목받고있는새로운형태의채널코딩기법이다. 최근들어 대 통신시스템뿐만아니라무선이지만네트워크로연결되어복수의단말기로이루어진시스템의통신용량에대한이론적한계가밝혀짐에따라, 이러한상황에적용할채널코딩기법에대한연구도활발하다. 위의 Raptor code 가이러한연구의중심에있다.

cup fills enough to quench your thirst With a digital fountain, a client obtains encoded packets from

36 FOUNTAIN CODING PRINCIPLE A digital fountain has properties similar to a fountain of water When you fill your cup from the fountain, you do not care what drops of water fall in, but only want that your cup fills enough to quench your thirst With a digital fountain, a client obtains encoded packets from one of more servers, and once enough packets are obtained, the client can reconstruct the original file

37 Information Encoder Sufficient output symbols are generated Decoder user user 3 user 2 Decoder BS Decoder user 4

38 RAPTOR CODES

recursive channel transformation taking polarization effects as below: N independent

39 Symmetric capacity Symmetric capacity 39 V. Polar Code Channel polarization a blockwise channel combining and splitting operation or a recursive channel transformation taking polarization effects as below: N independent copies of a given B-DMC W New set of N channels W i N () i N : Noise free!! Channel Polarization Channel index Channel index Completely noisy!!

40 24 년추가 (/2) ECC for Flash Memory 통신시스템과달리전혀다른접근이필요 반도체에서 과 을기억시키는방법에대한심도있는고찰이필요함 최근매우각광받고있는분야

41 24 년추가 (2/2) 본래의목적이아닌응용분야 Cryptography ECC-based Cryptosystem LPN: Learning Parity with Noise Cancellable Biometrics Distributed Video Coding

42 PART 4. 결론

43 V. 결론 채널코딩분야의연구활동에는서로다른두가지면이존재한다. 첫째는주어진 ( 동작하는 ) 통신시스템의성능을증가시키기위하여이미알려진채널코드의목록에서적당한채널코딩기법을선택하여오류성능 / 주파수대역 / 복잡도등의 spec 을충족하도록시스템을완성하는작업이다. 이는통신시스템엔지니어링의매우중요한한부분이다. 모든채널코드는실제로전송하고싶은정보비트 k 개를 n 비트의코드로변환한다. 이때, () n 과 k 를설정하는작업, (2) n 과 k 의비율 [k/n = code rate] 을정하는작업, (3) 설계한채널코드의디코딩복잡도를분석하는작업등이따져야할중요한항목이다. n 의절대적크기는디코더의속도와연관되어시스템의복잡도와직결되어있고, n 과 k 의비율 (code rate) 은통신시스템의주파수대역폭뿐만아니라코드의오류정정능력과관련이있으며, 채널코드의오류정정능력은전체통신시스템의오류성능과관련이있다. 여기서, 주파수대역폭을줄이자면 code rate 을크게해야하고, 그러면오류정정능력이줄고, 반대로오류정정능력을키우자면 code rate 을줄여야하고, 그러면주파수대역폭이늘어나게된다. 또한, n 을크게정하면디코딩복잡도가커져서이는전체시스템의복잡도를증가시킨다. 이러한관계속에서적절한균형을이루면서도원하는 system spec 을모두만족시키기란쉽지않은과제이다.

44 둘째는새로운채널코드를찾거나 ( 혹은, 발명하거나 ) 이미알려진채널코드의새로운성질 ( 오류정정능력, 디코딩복잡도, 등등 ) 을밝혀내는작업이다. 이는상당히기초적인탐구영역에속하는연구활동이며순수연구라고볼수있다. 언제그리고어떤방법으로이용될지는모르지만성능 ( 오류정정 / 주파수대역 ) 과복잡도면에서우수한채널코드를개발하여다양한특성을분석하고찾아내는작업은어떤면에서순수과학연구와비슷한과정을겪게된다. 심지어응용수학연구의한분야로분류되기도하는데, 여기에는정말다양한수학분야의이론들이기초적인배경을이루게된다. 앞서언급한몇가지코드들은 (Hamming 코드, BCH 코드, RM 코드, RS 코드, Convolution 코드, Turbo 코드, LDPC 코드, Raptor 코드, 등등 ) 모두이러한연구노력의결실이다. 재미있는사실은위의두가지면이서로에게밀접한영향을끼친다는사실이다. 시스템구성을위한좋은코드를찾는과정에서새로운코드를개발하기도하고, 순수하게수학적으로정의된좋은코드를발전시키다보니특정시스템에매우적합하게응용되어빛을발하는경우도있다는뜻이다.

45 채널코딩에관한연구는시대적으로항상 미래통신기술 의핵심을이룬다. 오늘날채널코딩이적용되지않은통신시스템은이제상상할수없는지경이다. 현재사용되고있는모든디지털통신시스템의국제 / 국내표준안에는반드시적절한채널코딩방식이들어있다. 이동통신 ( 핸드폰 ), 이동인터넷통신 ( 와이브로및와이맥스 ), 태양계및우주탐사위성통신, 통신방송을위한위성통신, 모든종류의군통신시스템, 지상파및위성 DMB, HDTV 방송통신, 디지털캠코더및 CD/DVD, MP3 파일, 심지어컴퓨터하드디스크나모든종류의디지털무선가전시스템의무선통신신호에까지채널코딩이널리사용되고있으니 앞으로우리가맞이할 IT 시대는가히 채널코딩의시대 라아니할수없다.

46 과목소개

47 Course Basic 일반대학원 Room B 39 Time 월 5,6,7 Professor Name 송홍엽 Song, Hong-Yeop URL Office B65 ( 제 2 공학관 ) Cell Phone office-hour hysong@yonsei.ac.kr office-hour : 월 8 (B65) Text : 통신공학을위한부호이론, 인피니티북스, 송영준, 구내서점구입가능 ( 강의록형식 ) Text 2: Essentials of Error-Control Coding, Wiley, Moreira and Farrell. 26 ( 강의록형식 ) Text 3: Fundamentals of Error Correcting Codes, Huffman and Pless. 23 (block code 계열 ) Text 4: Error Control Systems for Digital communications and storage, Wicker. 995 (block and conv) Text 5: Trellis and Turbo Coding, Wiley, Schlegel and Perez, 24 (convolutional code 계열 ) Text 6: Iterative Error Correction, Cambridge, Johnson, 2 (LDPC and Turbo code 계열 ) Error-correcting codes 47

48 왜 ECC 를공부하는가? 채널코딩에관한연구는시대적으로항상미래통신기술의핵심을이룬다. 오늘날채널코딩이적용되지않은통신시스템은이제상상할수없다. 현재사용되고있는모든디지털통신시스템의국제 / 국내표준안에는반드시적절한채널코딩이들어있다. 본래의목적 : 이동통신 ( 핸드폰 ), 이동인터넷통신 ( 와이브로및와이맥스 ), 태양계및우주탐사위성통신, 통신방송을위한위성통신, 지상파및위성 DMB, HDTV 방송통신, MP3파일, 디지털캠코더및 CD/DVD, 모든종류의군통신시스템, 컴퓨터하드디스크를비롯한 distribute storage systems for big data Solid State Drive System Reliability ECC for Flash Memory 모든종류의디지털무선가전시스템의무선통신신호 본래의목적이아닌목적 Cryptographic algorithm: Some Public-Key Cryptosystem (McEliece, LPN, etc) 생체인식암호시스템 : reliability of AD conversion process Distributed Video Encoding: 연관화면의일부전송후 ECC-decoding 으로전체를복구 48

49 Classification of ECC Code Structure Block code vs Tree code Linear code vs Non-linear code Binary code vs Non-binary code Single vs Concatenated Encoding Systematic vs Non-systematic Decoding Complete vs Incomplete Hard-decision vs Soft-decision Algebraic vs Probabilistic Iterative golay codes BCH codes RS codes Walsh-Hadamard Codes RM codes LDPC codes convolution codes turbo codes Block/linear Tree Song Error Correcting Codes 49

9월 일 Lecture 과목소개와채널코딩발전과정에대한간략한소개 9월 8일 ( 추석연휴휴강 ) 9월 5일 Lecture 2 Introduction to error-correcting codes Project # 9월 22일 Lecture 3 Fundamentals of binary linear block codes Project #2 9월 29일

codes and non-binary RS codes Project #5 월27일 Lecture 7 Hadamard codes and RM codes Project #6 월 3일 Lecture 8 Convolutional codes structures and encoding/decoding Project #7 월 일 Lecture 9 Turbo codes

50 9월 일 Lecture 과목소개와채널코딩발전과정에대한간략한소개 9월 8일 ( 추석연휴휴강 ) 9월 5일 Lecture 2 Introduction to error-correcting codes Project # 9월 22일 Lecture 3 Fundamentals of binary linear block codes Project #2 9월 29일 Lecture 4 Introduction to Finite Fields Project #3 월 6일 Lecture 5 Cyclic codes over Finite Fields and Meggit Decoder Project #4 월3일 ( 중간시험기간 중간시험없음 ) 월2일 Lecture 6 Algebraic Decoding of binary BCH codes and non-binary RS codes Project #5 월27일 Lecture 7 Hadamard codes and RM codes Project #6 월 3일 Lecture 8 Convolutional codes structures and encoding/decoding Project #7 월 일 Lecture 9 Turbo codes properties and encoding 월 7 일 Lecture Turbo codes - decoding Project #8 월 24 일 Lecture LDPC codes structures and encoding 2월 일 Lecture 2 LDPC codes message-passing decoding Project #9 2월 8일 Lecture 3 LT codes and Raptor codes Project # 2월5일 ( 기말시험기간 기말시험없음 ) some other applications of error-correcting codes ( 기회가된다면...) 5

51 Evaluation Mechanics Midterm/final exam: 없음 Project Report: 2 점 (2 점 x 회 ) 대략격주공지되며, 공지후제출마감은다음수업시간시작직전. 지각으로인하여당일제출임에도마감이지나는경우 % 삭감. 마감이후 일후부터 주일이내제출시 3% 삭감. 그이후는받지않습니다. 지각없이전출 : 5 점 ( 지각 회이상전출 : 3 점 ) 수업시간중 Extra Optional Problem: 대략 5 점 x n 회 = 5n 점 ( 최소 5 점, 최대 4 점 ) 총점 : 22 점. () 절대평가 (2) 상대평가 ( 절대평가불가능시 ) 55 점이상 (7% 이상 ): A+,A,A- 상위 4% : A+,A,A- 점이상 (5% 이상 ): B+,B,B- 중위 5% : B+,B,B- 점미만 (5% 미만 ): C or F 하위 % : C or F 성적과관계없는 F 학점조건 무단결석 2 회 사유가있는결석은무단결석이아님. 사유서제출필수. 수업중핸드폰혹은컴퓨터조작 수업중다른작업 ( 타과목시험공부등.) 5

52 Preparation of all your report Use A4 size paper and only one-side. Staple once at the top-left corner. Put your name and Student id number at the top of the first page. Write down in your own handwriting the following: 이보고서를작성하는과정에어떤부정행위도하지않았습니다. ( 서명 ) 날짜. I promise that this work was done only by myself. and SIGN, and put DATE 위형식을지키지않으면 % 추가삭감합니다. Due time is always the BEGINNING OF CLASS of the due day. Late submission rule: Due time 이후당일제출 ( 지각혹은망각등의사유 ) % 삭감 Due time 이후그다음날부터 주일이내 3% 삭감 그이후는받지않습니다. 52

53 제출방법 : Initial HW due: Week Friday hysong@yonsei.ac.kr subject: 오류정정부호수강생인사 홍길동 제출물 : JPG file of your face + 자기소개의글 + 지도교수님 성함 주의사항 : 추가점수는없지만마감을넘기는경우총점에서 점삭감. 53

54 수강생유의사항 (/2) 모든문의사항은이메일 로보내세요. 제목에반드시 "24-2 ( 오류정정 부호 ) 홍길동 - 문의내용제목 " 을사용하고서명, 학번과날짜를기록하세요. 위의형식을갖추지못한문의에는답변하지않습니다. OFFICE-HOUR란수강생여러분을위한시간입니다. ( 면담시간이아닙니다 ) 이시간에는내가방 ( 제2공학관 65호 ) 문을열어놓고여러분을기다립니다. 따로방문예약이나이메일보내지말고그냥오세요. 수업관련뿐만아니라담소를나누고싶어도환영합니다 이번학기본과목수강생여러분을위한 OFFICE-HOUR는월요일수업직후 8교시입니다. OFFICE-HOUR 이외의시간에는가급적나를찾지마세요 ^^ 연세대학교는부정행위에대해심각한학칙을적용하고있습니다. 보고서작성과정에다음이확인되면성적처리에불이익이있습니다.. 동료수강생의내용을 ( 일부라도 ) 카피하는일 ( 양자모두 F학점 ) 인터넷에올라있는보고서를자기것으로제출하거나인터넷에서검색한내용의일부문구를그대로카피하는일 ( 상황에따라서학점제한 ) 기타일체의부정행위 ( 상황에따라서학점제한 ) 54

55 수강생유의사항 (2/2) 모든수업은처음 5 분이매우중요합니다. 이부분을놓치지마세요.^^ 수업시간에지각하지마세요. 적어도 분전까지도착하겠다는계획을세우세요. 무단결석을피하려면다음을잘숙지하고지켜야합니다. 수강변경기간이후무단결석 2회면 F학점입니다. 반드시전날까지이메일혹은문자메시지로 ( ) 결석함을간략히통보하는데이때성명 / 학번 / 결석일을표시하기바랍니다. 당일통보는긴급상황이외에는인정하지않습니다. 한시간혹은장기간결석을마치고출석하게되어처음수업에참여하는날에는 ( 혹은그이전에라도 ) 수업시간시작전까지결석계를이메일로제출하세요. 이메일제목에는 24-2 ( 오류정정부호 ) 홍길동 - 결석계 " 라고정확히기입하고, 결석사유를자세히설명하기바랍니다. 수업시간중일체의질문을환영합니다. 조금이라도궁금하다면언제고맘편하게질문하세요. 한사람의 ( 멋진혹은엉뚱한 ^^) 질문이전체수강생의수업효과를높입니다. 교재의해당부분을반드시예습하고수업에참여하기바랍니다. 예습하지않는다면수업효과가많이줄어듭니다.^^ 수업시간에는핸드폰이나컴퓨터의사용을금지합니다. 반드시 turn-off 하기바랍니다. 소리가울리거나컴퓨터를조작하다가지적받으면곧바로 F 학점입니다. 55

56 Projects 목표 : Ideal BPSK 성능대비 coding gain을나타내는 BER 성능곡선찾기 요구사항 : BER 성능곡선과간단한분석을포함하는보고서 Program source와겉표지제외하고항상 4페이지이내로작성. 한글HWP 혹은 MS WORD 사용. 원본서식과 PDF 형식으로모두제출 ( 이메일과 hardcopy출력본 ) List of Codes TBA 보고서 hardcopy 마감은정확히 주일후수업시간시작전 당일이라도수업중혹은수업마치고제출하면감점있습니다. 동료수강생의소스프로그램을카피하여사용하면 F 학점입니다. 직접작성하거나인터넷검색을활용하여다운받은후이를변형하여사용해도무방합니다만, 이경우출처를밝혀야합니다. copyright@hong-yeop Song Error Correcting Codes 56

57 The end Hong-Yeop Song

Sequences with Low Correlation

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