저자소개송상훈연세대학교전자공학과학사한국과학기술원전산학과석사 University of Minnesota 전산학과박사 ETRI 연구원현세종대학교컴퓨터공학과교수 한동일고려대학교전자전산공학과학사한국과학기술원전기및전자공학과석사한국과학기술원전기및전자공학과박사 LG전자 DTV연구소

저자소개송상훈연세대학교전자공학과학사한국과학기술원전산학과석사 University of Minnesota 전산학과박사 ETRI 연구원현세종대학교컴퓨터공학과교수 한동일고려대학교전자전산공학과학사한국과학기술원전기및전자공학과석사한국과학기술원전기및전자공학과박사 LG전자 DTV연구소책임연구원현세종대학교컴퓨터공학과교수 논리회로설계 초판인쇄 205년 2월 23일초판발행 205년 2월 30일지은이송상훈 한동일펴낸이김승기펴낸곳 ( 주 ) 생능출판사 / 주소경기도파주시광인사길 43 출판사등록일 2005년 월 2일 / 신고번호제406-2005-000002호대표전화 (03)955-076 / 팩스 (03)955-0768 홈페이지 www.booksr.co.kr 책임편집신성민 / 편집최일연, 손정희, 김민보 / 디자인유준범마케팅백승욱, 최복락, 김민수, 심수경, 최권혁, 백수정, 최태웅, 김민정인쇄 제본 ( 주 ) 상지사P&B ISBN 978-89-7050-860-3 93560 정가 27,000원 이도서의국립중앙도서관출판예정도서목록 (CIP) 은서지정보유통지원시스템홈페이지 (http://seoji.nl.go.kr) 와국가자료공동목록시스템 (http://www.nl.go.kr/kolisnet) 에서이용하실수있습니다. (CIP 제어번호 : CIP205034504) 이책의저작권은 ( 주 ) 생능출판사와지은이에게있습니다. 무단복제및전재를금합니다. 잘못된책은구입한서점에서교환해드립니다.

머리말 이책은컴퓨터공학또는전자공학에서논리회로설계와관련된과목의교재로사용할수있도록내용을구성하였고, 총 장으로이루어져있다. 장은수체계를포함하여디지털시스템을소개하고, 2~6장은조합회로에관련된내용을다루고 7~장은순차회로부분을설명하고있다. 책을구성하고있는내용중 3.2 절의 Quine-McCluskey 방법, 4.9 절의논리회로구현기술, VHDL에관련된 6장과 장은다른내용을학습하는데관련없이생략할수있는부분이므로강의속도에맞추어적절히조절할수있을것으로생각된다. 각장은논리회로의핵심적인내용들을이해하기쉽고빨리습득할수있도록되도록간결하게설명하였고, 설명한내용의이해를돕기위한적절한예제들을수록하였다. 그리고각장의끝에단원요약부분이추가되어정리된내용을쉽게파악할수있도록하였다. 각장에포함된연습문제는장에서설명한내용들과비슷한수준의문제들로구성되어있고, 조합회로설계와순차회로설계와관련된장에는일부난이도가높은것들도포함되어있다. 부록에는부울대수정리, 게이트기호와진리표, 플리플롭기호및특성식과여기표, 표준칩들의핀배치, 실습을위한 logisim 사용법과실습내용, VHDL 코드의검증을위한시뮬레이터툴인 ModelSim에대한내용을첨부하였다. 이책은대부분의논리회로교재와다르게 VHDL에대한내용이포함되었다. 회로도에기반한논리회로를이해하는것도중요하지만점차 VHDL에의한시스템설계가많이이루어지고있기때문에논리회로설계에서 VHDL의중요성을인식시키고, VHDL 언어의특징과중요기능을짧은시간에습득할수있도록 6장에 VHDL을이용한조합회로설계와 장에 VHDL을이용한순차회로설계부분을추가하였다. 3

저자가디지털시스템을가르쳐오면서강의와관련된실습을진행할때에실습도구선택과교재에없는실습자료를준비하는어려움이있었다. 실제브레드보드를사용하여실습하는것은시간이너무많이걸리고, 일부타이밍다이어그램기반의시뮬레이터는회로의정확한동작을검증하기에는적합하지만학생들로부터흥미를유발시키기가어렵다. 하지만 JAVA 기반의교육용으로만들어진 logisim 시뮬레이터는 GUI 인터페이스가잘되어있어실습진행에시간적으로효율적이고, 7segment, LED, 클럭, Hex 표시장치, 스위치입력장치등이컴포넌트로제공되어브레드보드를사용하여실습하는것과같은흥미를유발시킬수있다. logisim 도구의또다른장점은 MS Windows, Mac OS, Linux 등의플랫폼에서실행되는무료소프트웨어라서학생들이쉽게사용할수있다는것이다. ModelSim 도구또한학생용무료버전을인터넷에서쉽게다운로드받을수있으며 VHDL로설계한논리회로의모든기능을매우쉬운사용자인터페이스를통해서상세한검증이가능한장점이있다. 부록 6에추가된 2가지실습은기본게이트동작및 logisim 사용법, 가산기 / 감산기, 비교기, 디코더, 우선순위인코더, 멀티플렉서, 4비트 ALU, 래치와플립플롭, 3상태버스를통한레지스터사이의데이터전송, 카운터, 자판기제어, 디지털시계들로이루어져있어강의와함께한학기동안실습을진행하기에부족하지않을것으로기대한다. 끝으로이책을완성하는데도움을준생능출판사여러분께감사드리고, 특별히책의구성및내용에대하여좋은의견을주신여러교수님들께도깊은감사를드린다. 205년 2월저자일동 4

차례. 디지털시스템과아날로그시스템 2.2 디지털신호의표현 5.3 인코딩 7 디지털시스템소개.4 수체계 9.5 2 진수연산 23.6 음수표현방법 26.7 BCD 코드 33.8 Gray 코드 35.9 문자코드 36.0 오류검출및정정코드 39 단원요약 44 연습문제 45 2. 기본연산과게이트 5 2.2 부울대수의정리 54 2.3 벤다이어그램표현 59 부울대수와논리회로 2.4 부울식과논리회로 6 2.5 부울식표현형태 67 단원요약 79 연습문제 80 5

3. 카노맵 88 3.2 Quine-McCluskey 방법 단원요약 26 부울식간략화 연습문제 27 4. 2 단회로와다단회로 33 4.2 NAND 와 NOR 게이트 35 4.3 NAND/NOR 게이트를사용한다단회로 42 논리게이트와구현기술 4.4 XOR 와 XNOR 게이트 44 4.5 전송게이트 49 4.6 버퍼와 3 상태버퍼 5 4.7 게이트지연과해저드 54 4.8 팬인과팬아웃제한 60 4.9 논리회로구현기술 6 단원요약 78 연습문제 80 6

5. 가산기 / 감산기 87 5.2 비교기 95 5.3 디코더 97 조합회로모듈과설계 5.4 인코더 202 5.5 멀티플렉서 204 5.6 디멀티플렉서 209 5.7 배럴시프터 2 단원요약 24 연습문제 25 6. VHDL 이란? 220 6.2 조합회로의설계 222 단원요약 256 VHDL을이용한조합회로설계 연습문제 257 7. 래치 265 7.2 클럭 273 7.3 플립플롭 274 플립플롭과레지스터 7.4 레지스터 289 단원요약 293 연습문제 294 7

8. 상태도와상태표 303 8.2 D 플립플롭의순차회로해석 308 8.3 JK 플립플롭의순차회로해석 3 순차회로해석 8.4 T 플립플롭의순차회로해석 34 8.5 Mealy 모델회로해석 37 단원요약 32 연습문제 322 9. 순차회로설계절차 327 9.2 플립플롭여기표 332 9.3 상태축소 343 순차회로설계 9.4 상태할당 35 9.5 one-hot 인코딩 356 단원요약 36 연습문제 362 0. 비동기식카운터 369 0.2 동기식카운터 374 0.3 시프트레지스터 38 카운터와시프트레지스터 0.4 시프트레지스터카운터 387 0.5 직렬가산기 39 단원요약 393 연습문제 394 8

. D 플립플롭 400.2 래치 407.3 카운터 40 VHDL을이용한순차회로설계.4 분주기 48 단원요약 428 연습문제 429 부록. 부울대수정리요약 438 2. 게이트기호와진리표 439 3. 플립플롭기호, 특성표, 특성식과여기표 44 4. 표준칩 442 5. logisim 사용법 446 6. 실습 460 7. ModelSim Tool 소개 485 찾아보기 496 9

CHAPTER 0 디지털시스템소개 contents. 디지털시스템과아날로그시스템.2 디지털신호의표현.3 인코딩.4 수체계.5 2진수연산.6 음수표현방법.7 BCD 코드.8 Gray 코드.9 문자코드.0 오류검출및정정코드

디지털시스템소개 단원개요 디지털시스템과아날로그시스템의차이점 디지털신호의표현방법과인코딩의필요성 2 진수, 6 진수등의수체계 2 진수음수표현방법과연산 BCD 코드, Gray 코드, 문자코드, 오류검출및정정코드 이장에서디지털시스템과아날로그시스템의차이와장단점에대하여설명하고, 디지털시스템에서논리값을표현하는방법, 디지털정보를효율적으로저장및처리를위한인코딩, 그리고디지털시스템에서다루는수체계및여러가지코드에대하여알아보기로한다. 디지털시스템에서다루는 2진수와관련하여 0진수, 2진수, 6진수등의수체계와 2진수에서음수표현방법인 부호화절대치, 의보수 그리고 2의보수 방식에대한장단점과관련된연산방법에대하여설명하고, 0진수를디지털시스템에서나타내기위한여러가지 BCD 코드와 Gray 코드, 문서의저장및전송을위한문자코드그리고오류검출및정정코드등에대하여소개한다.. 디지털시스템과아날로그시스템 디지털시스템은이산값 (discrete value) 을나타내는디지털신호를처리하는장치들을뜻한다. 반도체집적회로 (integrated circuit) 기술이눈부시게발전하면서디지털시스템은전자와정보통신분야뿐만아니라산업전반에걸쳐서광범위하게사용되고있다. 일상생활에서쉽게접할수있는스마트폰, 개인용 PC, 전기밥솥, 세탁기, 청소기및자동차엔진등의여러가지장치에내장되어있다. 시, 분, 초의시간을숫자로나타내는장치를가지고있는디지털시계는대표적인디지털시스템으로초단위의이산값만을 2 논리회로설계

나타내게된다. 이산값을나타내는디지털신호는보통 0 또는 의값을갖는비트 (bit: binary digit) 들로표현한다. 우리가가지고있는손가락 0개로수를셀때손가락을구부려사용하는, 2,, 0의신호도한정된신호를나타내는디지털신호라고할수있다. 디지털이란의미도세는데사용하는손가락또는아라비아수라는의미의 digit에서유래되었다. 이와대응되는아날로그시스템은연속적인값을갖는아날로그신호를처리하는장치들이다. 예를들어현재시간을시, 분, 초침의위치로나타내는아날로그시계의경우는초눈금사이에도이론적으로무한히많은시간을나타낼수있다. Am 0 : 08 5 (a) 아날로그시계 (b) 디지털시계 I 그림. 아날로그와디지털 [ 그림.2(a)] 는전자회로에서연속적인값을갖는아날로그신호의한예를보여주고있다. 그러나디지털시스템의신호는 [ 그림.2(b)] 처럼두가지전압 ( 예, 0V와 5V) 으로 0 과 의값을나타낸다. 일정범위의여러가지의디지털값을나타내기위해서는비트들의열인 2진수로인코딩 (encoding) 하여값을표현하게된다. V V 0 0 0 (a) 아날로그신호 I 그림.2 아날로그신호와디지털신호 t (b) 디지털신호 t 저울에서바늘눈금의위치, 움직이는자동차의속도, 성악가가내는음성의크기등과같이자연현상에서정량적으로측정할수있는것들은연속적값을나타내는아날로그 chapter 0 디지털시스템소개 3

신호이다. 그런데왜우리는아날로그신호를디지털신호로바꾸어디지털시스템으로처리하는가? 디지털시스템은아날로그시스템에비하여다음과같은여러가지의장점이있기때문이다. 설계 용이 : 아날로그회로의설계및분석을위하여트랜지스터, 인덕터, 캐패시터들을모델링하는고급공학수학이필요하지만디지털시스템의경우는논리 0와 을이용한부울식정도의수학만이필요하다. 잡음여유 (noise margin): 아날로그시스템은연속적인값을나타낼수있는신호를다루기때문에잡음과신호의구분이어렵지만이산적인값을다루는디지털시스템은신호 0과 을구분만할수있으면되므로잡음에의한영향을적게받는다. 즉, 디지털시스템은잡음에대하여민감하지않아잡음여유가크다고말할수있다. 재생성 (reproducibility): 아날로그회로는동일한입력임에도불구하고온도, 습도, 전압등의요인에의하여출력이달라질수있는데, 디지털시스템은이런외부요인에영향을받지않고같은입력에대하여항상같은출력을만들어낸다. 경제성 : 반도체기술의발전으로집적도가높아져서사용하는부품수가줄어들고, 대량생산이용이하여부품가격이낮아지고제작비용이줄어들어경제적이다. 프로그램 가능 : 고급프로그래밍언어와비슷한하드웨어기술언어인 HDL(verilog 또는 VHDL) 프로그래밍을통하여디지털회로를설계할수있다. HDL 프로그램으로설계된회로를 CAD(Computer Aided Design) 툴을이용하여 FPGA(Field Programmable Gate Arrays) 나 CPLD(Complex Programmable Logic Devices) 와같은프로그램가능한칩에구현할수있기때문에, 개발단계에서설계변경및수정작업등이쉽다. 아날로그신호를디지털시스템에서처리하기위해서는 [ 그림.3] 과같이입력에서아날로그신호를디지털신호로변환하는 A/D 변환기가필요하고, 출력에서디지털신호를아날로그신호로변환하는 D/A 변환기가필요하게된다. A/D 디지털시스템 D/A I 그림.3 디지털시스템입력과출력 4 논리회로설계

A/D 변환기는일정한주기로입력신호값을샘플링 (sampling) 하고, 샘플링한값을 2 진수로변환하여나타내는데비트열의길이에따라주어진범위내에서나타낼수있는값의정밀도가달라진다. [ 그림.4] 는 0V에서 7V 사이의입력신호를 3비트의디지털신호로변환한경우를보여주고있다. 디지털값은주어진비트로나타낼수있는근사값으로나타내기때문에원본신호와차이가발생하게되지만비트수를충분히크게하고, 입력신호를샘플링하는속도를충분히빠르게하면원본아날로그신호와거의차이가없는신호를재생할수있다. 7 6 5 7 6 5 0 0 4 3 2 4 3 2 0 00 I 그림.4 A/D 변환.2 디지털신호의표현 디지털시스템에서사용하는 2진값을물리적으로표현하는방법은다양하다. 예를들어 2진값인 0과 을회로내에서의 0V와 5V의전압레벨, 입력스위치의위방향과아래방향, 전등의 off와 on 상태, 또는자계의방향인 N-S와 S-N 등으로나타낼수있다. 이책에서는이러한물리적표현방법을가지고다루지않고, 논리값인 0과 을가지고논리회로해석및설계를하게될것이다. 디지털시스템에서 on/off 동작에필요한스위치기능은반도체인 MOSFET(Metal Oxide Silicon Field Effect Transistor) 를이용하여구현할수있다. [ 그림.5] 는 MOSFET의 nmos와 pmos의두가지타입의트랜지스터를보여주는데, 입력단자인 Gate의신호에따라 Drain과 Source 사이의스위치가 on/off 동작을하게된다. chapter 0 디지털시스템소개 5

Drain Drain Gate Gate (a) nmos Source Source (b) pmos I 그림.5 MOSFET [ 그림.6] 은 nmos 의 on/off 동작을나타내는그림이다. Gate 입력단자에논리값 에 해당하는 5V 가입력되면스위치가닫힌것처럼 Drain 과 Source 가연결이되고, 논리값 0 에해당되는 0V 가입력되면두단자가끊어진것처럼동작한다. Drain Drain 5V 0V Source (a) on Source (b) off I 그림.6 nmos 의 on/off 동작 pmos의경우는이와반대로 Gate 입력단자에논리값 0에해당하는 0V가입력되면스위치가닫힌것처럼 Drain과 Source가연결이되고, 논리값 에해당되는 5V가입력되면두단자가끊어진것처럼동작한다. 이런스위치역할을할수있는 nmos와 pmos 트랜지스터두가지를같이사용하는기술을 CMOS(Complementary MOS) 기술이라한다. CMOS 기술을사용하여논리함수를구현하는여러가지논리게이트 ( 논리함수모듈 ) 를만들수있는데, [ 그림.7] 은입력이 0이면출력이 이되고, 입력이 이면출력이 0이되는간단한인버터게이트내부회로를보여주고있다. +5V V i V o I 그림.7 CMOS 인버터 6 논리회로설계

[ 그림.8] 은논리게이트의출력과입력의전압범위가차이가나서잡음여유가크다는것을보여주는그림이다. 출력은논리 을 V oh(min) 에서 5V 사이의값으로, 그리고논리 0은 0V에서 V ol(max) 사이의값으로나타낸다. 즉, V oh(min) 은출력에서논리 인경우에허용되는최솟값이고, V ol(max) 는출력에서논리 0인경우에허용되는최댓값이다. 회로내에서입력은 V ih(min) 에서 5V 사이이면논리 로받아들이고, 0V에서 V il(max) 사이의값은논리 0으로인식한다. V ih(min) 은입력에서논리 로받아들여지는최솟값이고, V il(max) 는입력에서논리 0으로받아들여지는최댓값이다. 그러나 V il(max) 와 V ih(min) 사이의입력값은논리 과논리 0을나타내는신호의정상범위를벗어나게되어논리 0 또는 을나타내지못한다. 입력에서논리 로받아들여지는범위 (V ih(min) 5V) 는출력에서논리 을나타내는범위 (V oh(min) 5V) 보다훨씬넓기때문에논리 에대한정상범위의출력은입력에서논리 로인식되는것을보장하게된다. V oh(min) 와 V ih(min) 의차이가잡음여유 (noise margin) 가되는데, 잡음여유보다작은잡음신호 (noise) 가출력신호에추가되어도이신호를받는입력에서논리값 로인식되는것이보장된다. 논리값 0에대하여도 V ol(max) 와 V il(max) 의차이만큼의잡음여유 (noise margin) 가있다. V oh(min) 5V 출력 잡음여유 논리 논리 V ih(min) V ol(max) 0V 잡음여유 V il(max) 논리 0 논리 0 I 그림.8 입출력전압범위및잡음여유.3 인코딩 디지털시스템에서텍스트문서, 음악정보, 이미지정보등을디지털데이터로표현하는것을인코딩이라고하는데, 이런종류의데이터들을쉽게공유하기위하여여러가지인코딩방식이표준으로정해져있다. 예를들어 MP3 음악, 이미지를포함하고있는동영상등에대한표준화된인코딩방식이있기때문에다양한음악플레이어, 동영상처 chapter 0 디지털시스템소개 7

리프로그램들이만들어져서편리하게정보를공유할수있게되었다. 정수 (integer) 를 2진수로표현하는것도하나의인코딩이라할수있는데정수의경우는표현하는비트길이에의하여수를나타낼수있는범위가정해진다. n비트로나타낼수있는경우의수가 2 n 가지이므로, 부호가없는수를나타내는경우는 0부터 2 n -까지나타내면된다. 음수도필요한경우는양수와음수를 /2 정도나누어양수와음수를할당하게되는데, 연산이필요한대부분의디지털시스템에서는일반적으로 2의보수 (2 s complement) 방식이라는방법으로음수를표현한다. 2의보수방식은다른방법에비하여덧셈및뺄셈을위한논리회로구현이쉽기때문이다. 이와관련된음수표현방법에대한내용은.6 절에서상세히설명하기로한다. 문자의경우도영문알파벳, 숫자문자, 특수기호문자등을 2진수로나타내는방법및웹브라우저에서다국어표현을위한인코딩방식들이표준으로정해져있다. 디지털시스템설계를위하여논리회로를다룰때에도인코딩문제가대두된다. [ 그림.9] 는입력신호가디지털이면서이미인코딩된경우로 비트를사용하여입력버튼스위치의 off/on 상태인 2가지를 0과 로나타내고있다. 0(off) (on) I 그림.9 on/off 버튼스위치 [ 그림.0] 은 7개의 on/off 버튼스위치로이루어진입력장치에서입력신호를인코딩하여효율적으로정보를나타내는경우이다. 입력할때에두개이상의버튼을동시에누르지못한다고가정하면, 버튼을누르지않은경우와 7개의버튼중어느한개가눌려진경우를구분하기위하여 8가지경우를나타낼수있는코드가필요하다. 이런경우에 3비트로 [ 그림.0] 과같이인코딩하여 8가지경우를나타낼수있다. 8 논리회로설계

000 00 00 0 I 그림.0 3 비트인코딩.4 수체계 일반적으로정수를표현할때자릿수표현 (positional number representation) 방법을 사용한다. 자릿수표현방법에서하나의수는숫자들의열로나타내는데, 각숫자는숫자열에서자신의위치에따라크기가결정된다. = n - n - 2 2 0 r n- n- n-2 N ( a a ga aa) n-2 = a # r + a # r + g+ a # r + a # r+ a r : 기수 (radix) a i : 계수 (coefficient) 0 # a i < r 2 2 0 즉, n자리로이루어진수 N의크기는각숫자의위치와각숫자자체의크기에의하여결정된다. 실생활에서사용하는 0진수의경우에숫자 235의의미는다음과같다. 235 0 = 2 0 2 + 3 0 + 5 2 진수의경우에적용하면 00 2 = 2 7 + 2 6 + 2 5 + 0 2 4 + 2 3 + 0 2 2 + 2 + = 28 + 64 + 32 + 8 + 2 + = 235 0 6진수인경우는 6가지의기호가필요하기때문에숫자 0부터 9까지 0개와알파벳 A 부터 F까지 6개를추가하여나타낸다. chapter 0 디지털시스템소개 9

A = 0, B =, C = 2, D = 3, E = 4, F = 5 예를들어 6 진수 2EA 6 의의미는다음과같이된다. 2EA 6 = 2 6 2 + 4 6 + 0 = 52 + 224 + 0 = 746 0 디지털시스템은비트로이루어지는 2진수정보들을다루기때문에디지털시스템에대한설계및분석을위하여 2진수와관련이있는 6진수그리고일상생활에서사용하는 0진수와의관계를잘알아둘필요가있다. 0진수에서 2진수로변환하는방법에대하여알아보자. 여러가지방법이있는데먼저나누기를반복하면서나머지값을취하여구하는방법이있다. 예를들어 43 0 을반복하여 2로나누면서나머지를취하면 00 2 를구할수있다. 2 43 2 2 나머지 =a 0 2 0 나머지 =a 2 5 나머지 0=a 2 2 2 나머지 =a 3 2 나머지 0=a 4 0 나머지 =a 5 다음은 75 0 를 2의지수승값들과비교하면서 2진수로변환하는방법을알아보자. 75 는 2 7 (28) 보다작고, 2 6 (64) 보다크다. 따라서 a 7 까지는 0이고 a 6 는 이된다. 75에서 2 6 (64) 를뺀나머지 에대하여도같은방법으로 은 2 4 (6) 보다작고, 2 3 (8) 보다크므로 a 5 와 a 4 는 0이고 a 3 는 이된다. 에서 2 3 (8) 을뺀나머지 3에대하여같은방법으로할수있지만, 3은 a 2 a a 0 에대하여 0로변환되는것을쉽게알수있으므로이값을 a 7 a 6 a 5 a 4 a 3 에붙여서최종 0000을구할수있다. 이방법을사용하기위해서는 2의지수승값들을잘알고있어야한다. 20 논리회로설계

75-64 (2 6 ) - 8 (2 3 ) - 3 2 (2 ) - (2 0 ) 0 a 7 a 6 a 5 a 4 a 3 a 2 a a 0 0 0 0 0 컴퓨터공학에서는 < 표.> 에있는 2의지수승값이많이사용되기때문에익숙해질필요가있다. I 표. 2의지수승 n 2 n 2 2 4 3 8 4 6 5 32 6 64 7 28 8 256 9 52 0,024 2,048 2 4,096 3 8,92 4 6,384 5 32,768 6 65,536 2진수에서 0진수변환은자릿수표현방법에서설명한수의크기를구하는방법으로계산하면된다. chapter 0 디지털시스템소개 2

00 2 = 2 5 + 0 2 4 + 2 3 + 0 2 2 + 2 + = 32 + 8 + 2 + = 43 0 6진수는컴퓨터공학에서 2진수와함께가장많이사용되는진법중의하나이다. 2진수로표현하면수의길이가길어불편하지만 6진수로나타내면수의길이가짧아져서편리하다. 6진수의각자릿수는 2진수 4비트와일치하기때문에 2진수를 6진수로또는 6진수에서 2진수로의변환이쉽다. 2진수에서 6진수로변환은 2진수의 LSB(Least Significant Bit: 최하위비트 ) 에서시작하여 4비트씩그룹으로묶어, 각묶은그룹에해당하는 6진수로대치하면된다. 4비트씩그룹으로묶다가마지막그룹은 4비트로맞추기위하여 MSB(Most Significant Bit: 최상위비트 ) 쪽으로 0을추가하면된다. 00 2 = 0000 = 2B 6 2 B 반대로 6 진수에서 2 진수로변환은역으로하면된다. 즉, 6 진수각자릿수를대응하 는 4 비트의 2 진수로변환하여 2 진수들을연결하기만하면된다. < 표.2> 는 0 진수, 6 진수, 2 진수간의변환표를보여주고있다. I 표.2 2 진수와 6 진수 0진수 6진수 2진수 0 0 0000 000 2 2 000 3 3 00 4 4 000 5 5 00 6 6 00 7 7 0 8 8 000 9 9 00 0 A 00 B 0 22 논리회로설계

2 C 00 3 D 0 4 E 0 5 F 0진수에서 6진수로변환은 2단계로 0진수에서 2진수로변환한후에 2진수를다시 6진수로변환할수있다. 또는 0진수에서 6진수로바로변환하는것은앞에서설명한 0진수에서 2진수로변환하는방법과같이나누기를반복하면서나머지를취하는방법으로하면된다. 다음그림은 9590를 6으로계속하여나누면서나머지를취하여 3BF 6 로변환하는과정을보여주고있다. 6 959 6 59 나머지 5=F=a 0 6 3 나머지 =B=a 0 나머지 3 = a 2 6진수에서 0진수변환은자릿수표현방법에서설명한수의크기를구하는방법으로계산하면된다. 3BF 6 = 3 6 2 + 6 + 5 = 768 + 76 + 5 = 959 0.5 2 진수연산 대부분의디지털시스템에서 2진수데이터에대한덧셈, 뺄셈, 곱셈그리고나눗셈연산이필요하다. 2진수연산도 0진수에대한연산과비슷한방법으로계산할수있는데이러한 4칙연산방법에대하여알아보기로하자. () 덧셈한자릿수의 2진수기본덧셈의경우에다음과같이 4가지경우가있다. 덧셈에서올림수 (carry) 가발생할수있기때문에 0진수덧셈처럼올림수는다음위자릿수에더해져야한다. 논리회로에서이와같이비트두개를더하는가산기를반가산기 (half adder) 라고한다. chapter 0 디지털시스템소개 23

+ 0 0 0 + 0 + 0 + 0 올림수 다음은 4 자릿수 2 진수의덧셈의예를보여준다. 00 올림수 0 (3 0 ) + 00 00 (9 0 ) (22 0 ) 4자릿수연산인경우에올림수에의하여 5자릿수결과가나오는경우를보여주고있다. 두자릿수이상의덧셈에서는아래자리에서올림수가발생하기때문에각자릿수에서연산은세개의비트에대한덧셈이필요하게된다. 논리회로에서이와같이세개의비트를더하는가산기를전가산기 (full adder) 라고하는데, 자세한내용은 2장에서다룬다. (2) 뺄셈덧셈에서마찬가지로한자릿수의 2진수뺄셈도 4가지경우가있는데, 뺄셈에서는 0진수뺄셈과마찬가지로빌림수 (borrow) 가발생한다. 0진수뺄셈에서하는것처럼빌림수는다음위자릿수에서빼야한다. 0-0 0 0 - 빌림수 - 0-0 다음은 4 자릿수 2 진수의뺄셈의예를보여준다. 빌림수 0 (3 0 ) - 0 00 (7 0 ) (6 0 ) 24 논리회로설계

오른쪽에서두번째자리의뺄셈에서빌림수가발생하여세번째자리에 을표시하였다. 이빌림수는세번째자리에서빼야되는수이다. 세번째자리는피감수와감수가모두 이고빌림수가있기때문에 (--) 이되어결과가 이되고, 빌림수가발생하여네번째자리에빌림수 을표시하였다. 네번째자리는피감수와감수가 과 0이고빌림수가있어서 (-0-) 이되어결과가 0이된다. (3) 곱셈 2진수곱셈은숫자가 0과 로만이루어지므로다음그림에보여주는 4가지기본곱셈을사용하여곱셈연산을하게된다. 0 0 0 0 0 0 0 다음은 3 = 43 에대한 4 자릿수 2 진수곱셈하는과정을보여주고있다. 0 0 0 0000 0 0 000 ( 0 ) (3 0 ) (43 0 ) 0진수에서와같은방법으로승수 (multiplier) 의각자릿수의수를피승수 (multiplicand) 와곱셈한결과를열에맞추어더함으로써곱셈결과를얻을수있다. 각자릿수의열에맞추어 2진수덧셈을할때에올림수가 이상이나올수있으므로다음과같이부분합을누적하면서계산하는것이쉽다. 행 : 2행 : 3행 : 4행 : 0 + 0000 00 + 0 0 + 0 000 부분합 부분합 결과 chapter 0 디지털시스템소개 25

(4) 나눗셈 2진수나눗셈도 0진수나눗셈과같은방법으로계산할수있다. 몫에들어가는숫자들이 0과 두가지만있으므로구구단을이용하는 0진수의경우보다쉽다. 피제수 00을제수 00로나누면몫이 0이고나머지가 00이되는과정을살펴보자. 피제수와제수를좌측에서자리맞춤을하여피제수의좌측 4비트 이제수 00보다크므로몫의첫번째비트가 이된다. 피제수에서제수를뺀나머지 0과피제수의좌측에서 5번째비트를내려서 00을만들어제수를자리맞춤하여다시크기를비교한다. 피제수부분이크므로몫의두번째비트도 이된다. 피제수부분에서제수를뺀나머지 과피제수의 6번째비트를내려서 0을만들어도제수보다작으므로, 몫의세번째비트가 0이되고피제수마지막비트를내려서 0을만들어제수와비교한다. 피제수부분이크므로몫의네번째인마지막비트가 이되고, 피제수부분에서제수를빼면 00이남는데이것이나머지가된다. 0 3 00 00 00 00 00 0 00 00 9 2 9 3 27 4.6 음수표현방법 대부분의디지털시스템에서양수와음수를나타내는부호가있는수를표현하는방법이필요하다. 부호없는 2진수의경우는 n비트로나타낼수있는 0부터 2 n- 까지 2 n 개의수를나타내게된다. n비트로부호가있는수를표현하려면 n비트로나타낼수있는 2 n 가지를양수와음수, 그리고 0에할당을해야한다. 음수에대한표현방법은보통부호화절대치 (signed magnitude), 의보수 ( s complement), 2의보수 (2 s complement) 방식의세가지로나뉘는데, 음수표현방법에따라 0의표현과연산회로의복잡도가다르다. 양수의경우는세방법모두동일하게부호없는 2진수처럼표현한다. 26 논리회로설계

() 부호화절대치 (signed magnitude) 방식부호화절대치방식은 0진수에서사용하는방법과비슷한것으로 n비트의 2진수에서첫번째비트가부호비트이고나머지 (n-) 비트가크기를나타낸다. n비트로나타낼수있는범위는 -(2 n- - ) 부터 +(2 n- - ) 까지인데, n비트로나타낼수있는최대 2 n 개보다하나적은총 (2 n -) 개의수를나타낼수있다. 이것은부호화절대치방식의단점으로 +0과 -0인두개의 0이존재하기때문이다. 이방식으로나타내는수에대한덧셈과뺄셈을하기위한연산회로는다른두방식에비하여복잡하다. 덧셈에서만일부호가같은경우는두수의절대치값을더하면되지만, 부호가다른경우는두수의절대치를비교하여큰수의부호를택하고큰수에서작은수를뺀값이크기가된다. 뺄셈은뺄수의부호를바꿔서덧셈을하면된다. 예제. 부호화절대치방식의음수표현 +37 = 00000-37 = 0000 +27 = 0-27 = + = 0000000 - = 000000 (2) 의보수 ( s complement) 방식 2진법에서보수는 의보수와 2의보수의두가지가있다. n비트로이루어진 2진수 N에대한 의보수, N 는다음과같이정의된다. n N= 2 --N 즉, N의 의보수, N 는 (n비트 ) 에서 N을뺀값을의미하는데, 2진수 N의각비트를반전시키면된다. chapter 0 디지털시스템소개 27

예제.2 의보수구하기 N N 0 000 000 0 00 00 00 00 의보수방식의음수표현은 의보수개념을사용하여음수를나타내는것이다. 양수는부호화절대치와같은방식으로표현하고, 음수는양수에대한 의보수로정의한다. 의보수방식에서 n비트로나타낼수있는정수범위는 -(2 n- -) 부터 (2 n- -) 까지인데, 부호화절대치방식과마찬가지로 0에대한두가지표현이존재하는단점이있다. 덧셈과뺄셈의연산은부호화절대치방식에비하여훨씬간단하지만 2의보수방식보다는복잡하다고할수있다. 예제.3 의보수방식의음수표현 +37 = 00000-37 = 000 +27 = 0-27 = 0000000 + = 0000000 - = 0 (3) 2의보수 (2 s complement) 방식대부분의디지털시스템에서음수표현을위하여연산회로를구현하기쉬운 2의보수방식을사용한다. n비트의 2진수 N에대한 2의보수, N * 는다음과같이정의된다. * n N = 2 - N= N + n비트로이루어진 N의 2의보수, N * 는 2 n 에서 N을뺀값을의미하는데, N + 로서 의보수를구한후에 을더하면된다. 즉, 2 진수 N 의각비트를반전시킨후에 을더 하여구할수있다. 28 논리회로설계

I 표.3 의보수와 2의보수비교 N N N * 0 000 00 000 0 0 00 00 00 00 00 0 2의보수방식의음수표현은 2의보수개념을사용하여음수를나타내는것이다. 양수는 부호화절대치 와같은방식으로표현하고, 음수는양수에대한 2의보수로정의한다. n비트로나타낼수있는정수범위는 -2 n- 부터 (2 n- -) 까지인데, n비트로나타낼수있는모든경우를포함하고있다. 앞에서설명한 부호화절대치 방식과 의보수 방식에서는 0에대한표현이 +0과 -0의두가지가존재하는데, 2의보수 방식에서는하나의 0만존재한다. 뒤에서연산방법에대하여설명하겠지만세가지음수표현방식중에서 2의보수방식에서의연산이가장간단하다. 이런장점때문에대부분의컴퓨터들은 2의보수방식으로음수를표현하고있다. 예제.4 2 의보수방식의음수표현 +37 = 00000-37 = 00 +27 = 0-27 = 000000 + = 0000000 - = 2 의보수방식의수에대한 0 진수변환은부호없는수와같은방법으로하는데, MSB(Most Significant Bit) 만크기가 -2 n- 로계산하면된다. N = (a n- a n-2 a 2 a a 0 ) 2 = a n- (-2 n- ) + a n-2 2 n-2 + + a 2 2 2 + a 2 + a 0 chapter 0 디지털시스템소개 29

예를들어, 0 = (-2 3 ) + 0 2 2 + 2 + = -8 + 0 + 2 + = -5 또다른방법으로, MSB가 인경우는음수이기때문에 2의보수를구하여이수에대한 0진수변환을하여 - 부호를붙여도된다. 0인경우에 MSB가 이기때문에음수이고, 0의 2의보수를구하면 00이되므로 00에대한 0진수변환인 5를구하여부호 -를붙이면 -5가된다. 2의보수로표현할비트수가증가하면부호비트만확장하면된다. 예를들어 +3과 -3 에대한 2진수표현이 4비트에서 8비트로늘어나는경우에부호비트만복사하여확장하면된다. 4비트 8비트 +3 : 00 000000-3 : 0 0 I 표.4 음수표현방법비교 (4비트) 2진수표현 부호화절대치 의보수방식 2의보수방식 0000 +0 +0 +0 000 + + + 000 +2 +2 +2 00 +3 +3 +3 000 +4 +4 +4 00 +5 +5 +5 00 +6 +6 +6 0 +7 +7 +7 000-0 -7-8 00 - -6-7 00-2 -5-6 0-3 -4-5 00-4 -3-4 0-5 -2-3 0-6 - -2-7 -0-30 논리회로설계

(4) 의보수방식에서연산 의보수방식에서덧셈연산은부호화상관없이두수를더한후에올림수가발생하면 을더해준다. 이를순환자리올림 (end-around-carry) 이라고한다. 뺄셈인경우는부호에관계없이감수의 의보수를더하면된다. 부호화절대치방법에비하면훨씬간단하지만순환자리올림이라는추가적인덧셈과정이필요한단점이존재한다. 다음은 의보수방식의덧셈의예를보여주고있다. 00 (5 0 ) 00 (-5 0 ) + 000 (2 0 ) + 0 (-2 0 ) 0 (7 0 ) 0 + 000 (-7 0 ) 다음은 의보수방식의뺄셈의예를보여주고있다. - 00 000 + + 00 0 000 00 ( 5 0 ) (-2 0 ) (3 0 ) - 00 0 + 00 000 00 (-5 0 ) (2 0 ) (-3 0 ) (5) 2의보수방식에서연산 2의보수방식에서덧셈연산은부호화상관없이두수를더하면되고, 뺄셈인경우는부호에관계없이감수의 2의보수를더하면된다. 의보수 방식의순환자리올림 (endaround-carry) 과같은추가적인덧셈연산이필요하지않고 MSB에서발생하는올림수는버리면된다. 다음은 2의보수방식의덧셈의예를보여주고있다. 00 (5 0 ) 0 (-5 0 ) + 000 (2 0 ) + 0 (-2 0 ) 0 (7 0 ) 00 (-7 0 ) 버림 chapter 0 디지털시스템소개 3

다음은 2 의보수방식의뺄셈의예를보여주고있다. 00 00 (5 0 ) - 000 + 0 (-2 0 ) 00 (3 0 ) 0 0 (-5 0 ) - 0 + 000 (2 0 ) 0 (-3 0 ) 버림 (6) 2의보수방식에서오버플로우오버플로우 (overflow) 는 n비트데이터에대한연산을한결과를 n비트로나타낼수없을때발생한다. 오버플로우는더하는두수의부호가같은경우만발생할수있는데, 더한결과의부호비트가바뀌게되면오버플로우가발생한것이다. 다음은더하는두수모두가음수인경우또는양수인경우에오버플로우가발생한예를보여주고있다. 0 00 + 0 (-5 0 ) (-4 0 ) (7 0 ) + 00 000 (5 0 ) (4 0 ) 00 (-7 0 ) 버림 -5와 -4를더한경우에 4비트결과에서부호비트가 0으로되어 +7처럼보이고있다. +5와 +4를더한경우도부호비트가 로되어 -7처럼보이고있다. 오버플로우발생여부를올림수를검사하여확인할수있는데, 오버플로우는 MSB와 MSB 아래자리에서의올림수가서로다를때발생한다. 즉, MSB에서발생한올림수를 c n, MSB 아래자리에서발생한올림수를 c n- 라고할때, 오버플로우는 c n c n- 일때발생한다. 앞의 -5와 -4를더하는경우에 c n 은 이고 c n- 은 0이기때문에오버플로우가발생한것이다. +5와 +4를더하는경우에도 c n 은 0이고 c n- 은 이기때문에오버플로우가발생한것이다. 32 논리회로설계

.7 BCD 코드 디지털시스템내부에서는 2진수를사용하지만입출력인터페이스는 0진수를사용하는경우가많다. 따라서입력에서 0진수를 2진수로변환하거나, 출력에서 2진수를 0진수로변환할필요가있다. 입출력에서이런변환을쉽게하기위하여 0진수를자릿수마다각각 2진수로변환하여저장하면될것이다. 즉, 0진수에사용하는 0가지숫자를 2진수로나타내기위하여 4비트를할당하여 0부터 9까지의 0개의숫자를코드화하여자릿수마다 4비트씩할당하여 0진수를나타내는것이다. 즉, 0진수 365는각자릿수마다 4비트씩할당하여다음과같이표현할수있을것이다. 00 00 00 3 6 5 이방법이가장일반적으로사용되는 842 코드라고하는 BCD(Binary Coded Decimal) 코드이다. 그외에도 542 코드, 3초과 (Excess-3) 코드, 2-of-5 코드등이있다. 842 코드와 542 코드는코드의각비트가위치에따라정해진크기를갖는가중치코드 (weighted code) 이다. 842 코드에서각비트의가중치가왼쪽위치부터 8, 4, 2, 의크기를, 542 코드에서는 5, 4, 2, 의크기를갖는다. I 표.5 BCD 코드 0진수 842 코드 542 코드 3초과코드 2-of-5 코드 0 0000 0000 00 000 000 000 000 000 2 000 000 00 000 3 00 00 00 000 4 000 000 0 000 5 00 000 000 000 6 00 00 00 000 7 0 00 00 000 8 000 0 0 000 9 00 00 00 000 가중치코드가 b 3 b 2 b b 0 이고각비트크기 (weight) 가 w 3 w 2 w w 0 라고하면다음과같이 chapter 0 디지털시스템소개 33

0 진수 N 은계산된다. N = b 3 w 3 + b 2 w 2 + b w + b 0 w 0 즉, 842 코드에서 00은 8 + 0 + 0 + = 9를나타내고, 542 코드에서는 5 + 0 + 0 + = 6을나타낸다. 542 코드에서 00도 6의값으로계산되지만표준으로정의된코드에포함되지않는다. 3초과 (excess-3, XS-3) 코드는 842 코드에 3을더해서만든코드로서자기보수 (self-complementary) BCD 코드라고도한다. 2진수에서 의보수를구하는것과같은방법으로 3초과코드의각비트를반전시키면 9의보수가만들어진다. 3초과코드는각비트의크기가정해져있지않아서가중치코드가아님을알수있다. 2-of-5 코드는 5비트를사용하고각코드내의 의개수가 2개로고정되어있다. 5비트로만들수있는 32가지패턴중에서 의개수가 2개인경우는 0가지이다. 이 0가지를 0진수 0부터 9까지코드로할당하여쓰는것이다. 데이터저장또는전송할때 5비트중의하나에서오류가발생하면 의개수가 개또는 3개가되므로데이터에오류가있음을알아낼수있어서오류검출용코드로사용하는데적합한코드이다. 2-of-5 코드도각비트의크기가정해져있지않아서가중치코드가아니다. 각 BCD 코드마다표준으로정해진것외의다른비트패턴들은사용하지않는코드들이다. 예제.5 0 진수 37 에대한 BCD 코드표현 842 코드 : 000 00 0 542 코드 : 000 00 00 3초과코드 : 000 00 00 2-of-5 코드 : 000 000 000 37 에대한 2 진수표현은 8 비트의 00000 로표현된다. 하지만예제.5 에보는것처럼 3 자리의 0 진수를표현하기위하여 BCD 코드는 2 비트또는 5 비트가필요하여저장 용량면에서비효율적이다. 34 논리회로설계

.8 Gray 코드 Gray 코드는숫자를나타내는코드를순서대로배열했을때인접한코드간에비트변 화가한번만발생하는코드이다. I 표.6 Gray 코드 0진수 Gray 코드 0 000 00 2 0 3 00 4 0 5 6 0 7 00 광학센서를통하여회전판의각도를알아내기위하여회전판에위치정보를나타내는 3비트 2진수순서대로인코딩한패턴이칠해져있다고가정하자. 경계선에서의 3비트각각은광학센서에어느쪽값이입력될지모른다. 이런경우에 3번과 4번사이의경계선에서입력값은 0에서부터 7까지모든경우가나타날수가있어오류값이커질수있다. 3 4 2 5 6 0 7 000 00 00 0 00 0 0 I 그림. 2 진수코드로인코딩 이런경우에 3 비트 Gray 코드로인코딩한패턴을이용하면경계선에서입력값은 3 또는 4 의경우만나타나게되어오류를최소화할수있게된다. chapter 0 디지털시스템소개 35

2 3 4 0 7 00 0 5 6 I 그림.2 Gray 코드로인코딩 Gray 코드는 MSB가 0인그룹과 인그룹이서로 MSB를제외한부분이반사된 (reflected) 특징을가지고있어서반사 2진코드 (reflected binary code) 라고도한다. 이런반사된특성을이용하여다음과같은방법으로 Gray 코드를완성할수있다. I. 비트 Gray 코드는 0과 이다. II. (n+) 비트 Gray 코드는먼저 n비트 Gray 코드순서대로맨앞에 0을붙여서 (n+) 비트 Gray 코드의반을완성하고, 나머지반은 n비트 Gray 코드의역순 ( 반사된순서 ) 으로맨앞에 을붙어서 (n+) 비트 Gray 코드를완성한다. 다음은 3비트 Gray 코드를반사하여만드는과정을보여주고있다. 비트 0 0 0 2 비트 00 0 0 00 0 0 0 0 00 3 비트 000 00 0 00 0 0 00.9 문자코드 () ASCII 코드디지털시스템에서처리하는자료는숫자뿐만이아니고문자도다루기때문에이들을 2 진코드로표현할수있어야한다. 키보드에서자료를입력하거나프린터로자료를출력하는경우에표준방식의문자코드가필요하여 960년대에미국표준협회 (American 36 논리회로설계

Standard Association) 는 7비트로정의된 ASCII(American Standard Code for Information Interchange) 코드를문자코드표준으로정하였다. ASCII 코드는국제표준문자코드로서텍스트파일전송및저장등에가장많이사용된다. < 표.7> 에보여주는 ASCII 코드는공백문자 (SP) 를포함한 95개의프린트가능한문자들과 33개의제어문자들로구성되어있는데, 많은제어문자들이과거의텔레타이프 (teletype) 용으로만들어진것들이어서잘사용되지않고있고일부는여전히통신제어용과프린터제어용코드등으로자주사용되고있다. I 표.7 ASCII 코드 b 7 b 6 b 5 b 4 b 3 b 2 b 000 00 00 0 00 0 0 0000 NUL DLE space 0 @ P ` p 000 SOH DC! A Q a q 000 STX DC2 2 B R b r 00 ETX DC3 # 3 C S c s 000 EOT DC4 $ 4 D T d t 00 ENQ NAK % 5 E U e u 00 ACK SYN & 6 F V f v 0 BEL ETB 7 G W g w 000 BS CAN ( 8 H X h x 00 HT EM ) 9 I Y i y 00 LF SUB * : J Z j z 0 VT ESC + ; K [ k { 00 FF FS, < L \ l 0 CR GS - = M ] m } 0 SO RS. > N ^ n ~ SI US /? O _ o DEL 예를들어문자 ABC 에대한 ASCII 코드는다음과같다. A: 00000 2 = 4 6 = 65 0 B: 00000 2 = 42 6 = 66 0 C: 0000 2 = 43 6 = 67 0 chapter 0 디지털시스템소개 37

(2) 유니코드 (Unicode) 유니코드는다국어환경에서문자에대한서로호환되는환경을제공하기위하여유니코드협회 (Unicode Consortium) 에서제정한표준인데, 문자집합, 문자인코딩등에관한표준이정의되어있다. 유니코드는문자에대하여 0 6 0FFFF 6 범위의코드번호를할당하여정의하고있고, 6진수코드에 U+ 접두어를붙여서나타낸다. 유니코드는 7개의유니코드영역 (Unicode Plane) 으로나뉘는데, 각영역은 2 6 개의코드로구성된다. I 표.8 유니코드영역과코드번호범위 기본 보조 영역 0 영역 영역 2 영역 3~3 영역 4 영역 5~6 기본다국어 (BMP) 보조다국어 (SMP) 보조상형문자 (SIP) 미지정 보조특수목적 (SSP) 보조사용자영역 0000~FFFF 0000~FFFF 20000~2FFFF 30000~DFFFF E0000~EFFFF F0000~0FFFF 기본다국어영역 (Basic Multilingual Plane, BMP) 은 U+0000부터 U+FFFF까지의 4자리 6진수가사용되고거의모든언어에대한문자들이포함되어있고많은부분이한글과한중일통합한자들이차지하고있다. 나머지영역들은 5자리또는 6자리 6진수를사용한다. ASCII 코드에해당하는코드는 U+0000부터 U+007F까지 ASCII 코드순서대로할당되어있다. 한글기본완성형글자들은 U+AC00부터 U+D7A3 까지할당되어있고, 한글자모등은다른영역에추가로할당되어있다. 유니코드번호는문자집합에속한모든문자에유일하게정의된번호이고, 이문자번호에대한인코딩방식인 UTF-8(Unicode Transformation Format), UTF-6, UTF-32 등의표준이정의되어있다. 가장많이사용되는 UTF-8 과 UTF-6은가변길이의인코딩방식으로문자에따라코드길이가달라진다. UTF-32는모든문자에 4 바이트의고정길이의코드로인코딩한다. 38 논리회로설계

.0 오류검출및정정코드 () 패리티 (parity) 비트데이터를전송할때, 데이터와연관된정보를추가하여전송하면수신측에서전송오류가발생했는지검출할수있다. 가장간단한방법으로전송하는데이터의 의개수를짝수 ( 또는홀수 ) 로만들기위하여패리티비트를추가하는것이다. 즉, 원래데이터에패리티비트를추가하여전송하면, 수신측에서수신한데이터의 의개수가짝수 ( 또는홀수 ) 인지확인하여 비트의전송오류가발생했는지알수있다. 2비트가동시에바뀌면전송오류를검출할수없지만, 비트오류에비하여일어날확률이아주낮다고가정하는것이다. 짝수패리티는패리티비트포함하여데이터의 의개수가짝수가되도록패리티비트를추가하는것이다. 반대로, 홀수패리티는패리티비트포함하여데이터의 의개수가홀수가되도록패리티비트를추가하는것이다. 패리티비트를 LSB에추가한다고가정할때 < 표.9> 는짝수패리티와홀수패리티예를보여주고있다. I 표.9 패리티비트 패리티포함한 8비트 7비트데이터 짝수패리티 홀수패리티 A = 00000 00000 0 00000 B = 00000 00000 0 00000 C = 0000 0000 0000 0 패리티비트는사용방법이간단하기때문에직렬데이터전송에서많이사용되고, 메모리와같은저장장치에도응용하여오류를쉽게찾을수있게한다. 그외에오류검출방식으로패리티비트방법을응용한 2차원패리티비트방식, 체크섬 (check sum), CRC(Cyclic Redundancy Check) 등이있다. (2) 해밍 (hamming) 코드 R. W. Hamming이고안해낸해밍코드는컴퓨터메모리시스템에많이사용되는오류정정코드인데 비트의오류가발생하면해당비트를정정할수있는코드이다. 해밍코 chapter 0 디지털시스템소개 39

드는 n비트의데이터에 k비트의패리티가추가되어 (n+k) 비트로만들어지는데, n과 k 의관계는다음과같다. k n+ k# 2 - < 표.0> 에보이는것처럼데이터비트길이 n 에대하여추가되는패리티비트는로그 함수로증가되어비트길이가긴데이터에대하여효율적이다. I 표.0 해밍코드에서추가되는패리티길이 n(data bit) k(parity bit) n+k(total) 2 3 4 3 7 4 5 26 5 3 57 6 63 20 7 27 8비트데이터 000 에대한해밍코드를만드는방법을알아보자. 8비트에데이터에대한패리티는 4비트 (P, P 2, P 4, P 8 ) 가필요한데각패리티비트의위치를다음과같이 b, b 2, b 4, b 8 의위치에배치하고나머지위치에 8비트데이터를순서대로배치한다. 비트위치번호는 b 0 이아니고 b 번부터시작하고있다. b b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 0 b b 2 P P 2 P 4 0 P 8 0 0 각패리티는다음과같이계산하여해밍코드를완성한다. 짝수패리티함수는인수에해당하는비트들의짝수패리티를계산한다고가정한다. P = 짝수패리티 (b 3, b 5, b 7, b 9, b ) = 짝수패리티 (, 0,, 0, ) = P 2 = 짝수패리티 (b 3, b 6, b 7, b 0, b ) = 짝수패리티 (,,, 0, ) = 0 P 4 = 짝수패리티 (b 5, b 6, b 7, b 2 ) = 짝수패리티 (0,,, ) = P 8 = 짝수패리티 (b 9, b 0, b, b 2 ) = 짝수패리티 (0, 0,, ) = 0 40 논리회로설계

저장할데이터는다음과같이패리티비트가추가된 2 비트가저장된다. b b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 0 b b 2 0 0 0 0 0 이렇게저장된 2비트를메모리로부터읽어서오류발생여부와정정하는방법을알아보자. 각패리티들은해당그룹의비트들에대한짝수패리티이다. 즉, 패리티비트를포함한해당그룹의 의개수는짝수이다. 즉, 해당그룹에 비트오류가있으면 이되고오류가없으면 0이되는체크비트를다음과같이계산하면오류비트위치도알수있다. C = 짝수패리티 (b, b 3, b 5, b 7, b 9, b ) C 2 = 짝수패리티 (b 2, b 3, b 6, b 7, b 0, b ) C 4 = 짝수패리티 (b 4, b 5, b 6, b 7, b 2 ) C 8 = 짝수패리티 (b 8, b 9, b 0, b, b 2 ) 예를들어, 다음과같이세가지경우에대하여체크비트를계산하면오류발생여부와오류가발생했을때의오류비트의위치를알수있다. b b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 0 b b 2 오류없음 0 0 0 0 0 비트 4 오류 0 0 0 0 0 0 비트 0 오류 0 0 0 0 오류가없는경우체크비트를계산하면다음과같다. C = 짝수패리티 (b, b 3, b 5, b 7, b 9, b ) = 짝수패리티 (,, 0,, 0, ) = 0 C 2 = 짝수패리티 (b 2, b 3, b 6, b 7, b 0, b ) = 짝수패리티 (0,,,, 0, ) = 0 C 4 = 짝수패리티 (b 4, b 5, b 6, b 7, b 2 ) = 짝수패리티 (, 0,,, ) = 0 C 8 = 짝수패리티 (b 8, b 9, b 0, b, b 2 ) = 짝수패리티 (0, 0, 0,, ) = 0 즉, 체크비트 C 8 C 4 C 2 C (0000) 는오류가없음을나타내고있다. 비트 4 에오류가있는경우체크비트를계산하면다음과같다. chapter 0 디지털시스템소개 4

C = 짝수패리티 (b, b 3, b 5, b 7, b 9, b ) = 짝수패리티 (,, 0,, 0, ) = 0 C 2 = 짝수패리티 (b 2, b 3, b 6, b 7, b 0, b ) = 짝수패리티 (0,,,, 0, ) = 0 C 4 = 짝수패리티 (b 4, b 5, b 6, b 7, b 2 ) = 짝수패리티 (0, 0,,, ) = C 8 = 짝수패리티 (b 8, b 9, b 0, b, b 2 ) = 짝수패리티 (0, 0, 0,, ) = 0 체크비트 C 8 C 4 C 2 C (000) 은비트 4가오류임을나타내고있다. 비트 0에오류가있는경우의체크비트를계산하면다음과같다. C = 짝수패리티 (b, b 3, b 5, b 7, b 9, b ) = 짝수패리티 (,, 0,, 0, ) = 0 C 2 = 짝수패리티 (b 2, b 3, b 6, b 7, b 0, b ) = 짝수패리티 (0,,,,, ) = C 4 = 짝수패리티 (b 4, b 5, b 6, b 7, b 2 ) = 짝수패리티 (, 0,,, ) = 0 C 8 = 짝수패리티 (b 8, b 9, b 0, b, b 2 ) = 짝수패리티 (0, 0,,, ) = 체크비트 C 8 C 4 C 2 C (00) 은비트 0이오류임을나타내고있다. 다음은데이터 비트와패리티 4비트로이루어진해밍코드에대하여각패리티그룹에속한비트들을나타내고있는데, 어느한비트에오류가발생하면해당그룹에대한패리티를검사하는체크비트가세트되어오류비트의위치를나타내게된다. b b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 0 b b 2 b 3 b 4 b 5 P P 2 D P 4 D 2 D 3 D 4 P 8 D 5 D 6 D 7 D 8 D 9 D 0 D P 그룹 P 2 그룹 P 4 그룹 P 8 그룹 각패리티그룹의패리티비트 P i 는해당그룹의데이터들에대한짝수패리티이다. 42 논리회로설계

예제.6 4 비트데이터 00 을해밍코드로인코드하라. (4 + 3) (2 3 - ) 이므로 4 비트데이터의경우 3 개의패리티비트 (P,P 2,P 4 ) 가필요하다. 각패리티비트의위치를다음과같이, 2, 4 의위치에배치하고나머지는 4 비트데이터를순 서대로배치한다. b b 2 b 3 b 4 b 5 b 6 b 7 P P 2 P 4 0 0 각패리티는다음과같이계산하여해밍코드를완성한다. P = 짝수패리티 (b 3, b 5, b 7 ) = 짝수패리티 (, 0, ) = 0 P 2 = 짝수패리티 (b 3, b 6, b 7 ) = 짝수패리티 (, 0, ) = 0 P 4 = 짝수패리티 (b 5, b 6, b 7 ) = 짝수패리티 (0, 0, ) = 완성된해밍코드는 0000 이된다. 예제.7 저장된해밍코드를읽은값이 00 이다. 오류가있으면정정하여데이터값을구하라. 저당된해밍코드에대한체크비트를계산하면다음과같다. C = 짝수패리티 (b, b 3, b 5, b 7 ) = 짝수패리티 (,,, ) = 0 C 2 = 짝수패리티 (b 2, b 3, b 6, b 7 ) = 짝수패리티 (0,,, ) = C 4 = 짝수패리티 (b 4, b 5, b 6, b 7 ) = 짝수패리티 (0,,, ) = 체크비트 C 4 C 2 C (0) 은비트 6 이오류임을나타내고있다. 따라서정정된해밍코드는 000 이고, 패리티비트를제외한데이터는 0 이다. chapter 0 디지털시스템소개 43

단원요약. 불연속적인값을다루는디지털시스템은 0과 의값을갖는 2진수비트들의열인 2진수로인코딩 (encoding) 하여값을표현한다. 2. 디지털시스템은아날로그시스템과비교하여설계용이, 잡음여유, 재생성, 경제성, 프로그램가능측면에서장점이있다. 3. 2진수의음수표현방식에세가지가있다. 부호화절대치방식은십진법에서사용하는방법과비슷한방법으로 n비트의 2진수에서첫번째비트가부호비트이고나머지 (n-) 비트가크기를나타내는데, +0, -0인두개의 0이존재하고연산회로를만들기가복잡한단점이있다. 4. 의보수방식은 의보수개념을사용하여음수를나타내는데, +0, -0인두개의 0이존재하는단점이있고, 덧셈, 뺄셈에대한연산에서순환자림올림 (end-around-carry) 이발생하는단점이있다. 5. 2의보수방식은 2의보수개념을사용하여음수를나타낸다. 덧셈, 뺄셈에대한연산회로를가장간단하게구현할수있다. 대부분의디지털컴퓨터들은음수를나타내는데 2의보수방식을사용한다. 6. 0진수를 2진수로나타내는 BCD 코드에 842, 542, Excess-3 코드, 2-of-5 코드등의여러가지들이있다. 이들중에서 842 코드와 542 코드는가중치코드이다. 7. Gray 코드는숫자를나타내는코드를순서대로배열했을때인접한코드간에비트변화가한번만발생하는코드이다. 8. 그밖에문자코드를나타내는 ASCII 코드와유니코드등이있다. 9. 패리티비트는데이터전송및저장할때정보를추가하여데이터를수신또는읽어올때, 데이터에 비트전송오류또는저장오류가발생했는지검출할수있게한다. 해밍코드는 비트오류가발생했을때해당오류를정정할수있는코드이다. 44 논리회로설계

연습문제 0 디지털시스템의장점을설명하라. 02 아날로그신호와디지털신호의차이점은? 03 아날로그신호와디지털신호의예를 3 가지씩들어라. 04 A/D 변환기와 D/A 변환기의역할은? 05 nmos 와 pmos 의기호를그리고 on/off 동작을설명하라. 06 CMOS 인버터회로를 nmos 와 pmos 를사용하여그려라. 07 잡음여유 (noise margin) 란? 08 키보드자판키에 40 개의키가있다고가정한다. 각키를나타내는코드로인코딩하 려고하려면최소몇비트가필요한가? 09 다음 0 진수들을 2 진수로변환하고, 6 진수로변환하라. a) 37 b) 370 c) 3700 d) 23 e) 09 0 다음 2 진수들을 6 진수로변환하라. a) 000 b) 0000 c) 0000 d) 00 부호가없는 2 진수를 0 진수로변환하라. a) 00 b) 0000 c) 00 d) 0 e) 000000 f) 00000 2 2 의보수방식을사용하는 2 진수들에대한덧셈결과를구하라. a) 00 + 00 b) 000 + 0000 c) 0000 + 00 d) + 00 chapter 0 디지털시스템소개 45

3 2 의보수방식을사용하는 2 진수들에대한뺄셈결과를구하라. a) 0000-00 b) 000-0000 c) 0-000 d) 0000-0000 4 부호없는 2 진수들에대한곱셈결과를구하라. a) 00 0 b) 00 00 c) 000 000 d) 00 5 부호없는 2 진수들에대한나눗셈결과를구하라. a) 00 0 b) 00000 00 c) 000000 000 d) 0000 00 6 다음수들을부호화절대치, 의보수, 2의보수방식으로부호비트포함하여 6비트로나타내라. a) -3 b) -8 c) -3 d) - 7 다음 0진수들에대한덧셈을 2진수로나타내라. 음수에대한표현은부호화절대치방식으로나타낸다. 부호비트포함하여 6비트로나타내고, 오버플로우발생여부를명시하라. a) 2 + 2 b) (-3) + (-8) c) (-20) + 9 d) (-3) + 4 8 다음 0진수들에대한덧셈을 2진수로나타내라. 음수에대한표현은 의보수방식으로나타낸다. 부호비트포함하여 6비트로나타내고, 오버플로우발생여부를명시하라. a) 2 + 2 b) (-3) + (-8) c) (-20) + 9 d) (-3) + 4 9 다음 0진수들에대한덧셈을 2진수로나타내라. 음수에대한표현은 2의보수방식으로나타낸다. 부호비트포함하여 6비트로나타내고, 오버플로우발생여부를명시하라. a) 2 + 2 b) (-3) + (-8) c) (-20) + 9 d) (-3) + 4 46 논리회로설계

20 메모리에저장된 2진수는해석하는방법에따라나타내는 0진수값이달라질수있 다. 다음각 2진수에대하여무부호수 (unsigned number), 부호화절대치, 의보 수, 2의보수방식으로해석할때나타내는 0진수값들은? a) 0000 b) c) 0000000 d) 0 e) 0 2 다음 0 진수들을 842 코드, 542 코드, 3 초과코드, 2-of-5 코드로나타내라. a) 234 b) 46 c) 92 d) 758 22 메모리에다음과같이저장된 2 진수가 842 코드, 542 코드, 3 초과코드일경우에 나타내는 0 진수값들은? a) 00000 b) 00000 23 다음문자에대한 ASCII 코드를 6 진수로나타내라. a) a b) F c) # d) 24 전송할문자에대하여홀수패리티를만들어전송하는경우에다음문자의 ASCII 코드에대한패리티비트를계산하라. a) a b) F c) # d) 25 데이터 을해밍코드로인코드하라. 26 저장된해밍코드를읽은값이 0 이다. 오류가있으면정정된해밍코드와데이 터값을구하라. 27 전송할데이터에서모든 0 은 00 으로, 은 로보내면수신측에서 비트오류를검 출또는정정할수있는지설명하라. chapter 0 디지털시스템소개 47