Study with me =)

과제로 부스 알고리즘을 사용해 볼 일이 있어서 알아봤는데 굉장히 흥미로웠다. 처음엔 오른쪽 시프트하고 부호 어떻게 채우는지 이해가 안돼서 굉장히 고생함ㅠㅠ

1. Booth's 알고리즘이란?

부호가 있는 이진수의 곱셈을 수행할 수 있도록 해주는 알고리즘으로, 영국의 컴퓨터과학자인 Andrew Donald Booth에 의해 개발되었다. 계산을 하기 전 계산에 사용되는 수에 대해 알아보자.

1.1. Booth's Algorithm을 이용한 계산에 사용되는 수

M x Q를 계산한다고 가정하자. 

• M = Multiplicant
• Q = Multiplier
• A = M의 bit수만큼 0으로 초기화한 후 계산에 사용하는 친구
• q0 = 계산에 사용하는 최하위 비트
• Count = loop를 돌리는 횟수로 계산하려는 2진수의 bit수이다.

1.2. Flowchart

아래 사진의 순서에 따라 loop를 돌며 곱셈의 결과를 도출할 것이다. 아래 예제를 보자.

2. Booth's 알고리즘을 이용한 음수 곱셈

2.1. 계산에 필요한 수 초기화 및 대입

(-12) x (30)을 6bits 곱셈으로 계산해 볼 것이다. 위 규칙에 따라 아래와 같이 초기화된다.

• M = -12의 2진수 표현 = 110100
• Q = 30의 2진수 표현 = 011110
• A = M의 bit수인 6자리를 0으로 초기화 = 000000
• q0 = 0으로 초기화 = 0
• Count = 계산하려는 2진수의 bit수 = 6

2.2. 계산과정

우리는 2.1.에서 정의한 'AQq0'를 Count만큼의 loop를 돌며 계산해 나갈 것이다. 

총 곱셈 과정에서 수행할 연산은 2's complement, Arithmatic right shift, 이진수 덧셈 세가지밖에 없으니 겁먹지 않아도 된다.

<모든 초기화가 끝난 상태>

이제 우리는 flowchart에서 봤던 것처럼 q1q0값이 무엇인지에 따라 아래 표를 채워나갈 것이다. 

현재 q1q0은 00이므로 flowchart의 아래로 내려가 AQq0에 대해 Arithmatic right shift를 수행하고 Count를 감소시킬 것이다.

<Count == 5 를 계산하는 중>

다음 q1q0는 이제 10으로 바뀌었다. 이번에는 flowchart의 왼쪽 화살표를 따라가 A = A - M 연산을 수행해야 한다.

A는 000 000이고 -M은 12, 즉 이진수로 001 100이다. 둘을 더하면 001 100일 것이다.

A = A - M 연산과 A = A + M 연산은 둘 다 덧셈 연산이다.
-M을 더하는지 M을 더하는지만 다르다고 생각하면 된다.

덧셈 계산을 수행한 다음 Arithmatic right shift를 수행하고 Count를 감소시켜야 한다. 

그 후 과정은 위에서 예시를 보였던 연산이므로 넘어가겠다.

Arithmatic right shift 연산을 할 때 왼쪽 공간에 채우는 숫자는 
A가 양수일 경우, 즉 첫비트가 0일 경우 0으로 채운다.
A가 음수일 경우, 즉 첫비트가 1일 경우 1으로 채운다.

<Count == 1 를 계산하는 중>

이번에는 q1q0가 01이 나왔으므로 A = A + M을 수행해야 한다.

M은 (-12)로, 이진수로는 110 100이다. 현재 A인 000 000과 더해주면 110 100이 나온다.

따라서 다음 A는 110 100이다. 계산을 마무리해 보자.

<완성된 표>

loop의 종료 조건인 Count == 0 이 만족되어 연산이 모두 끝났다.

AQ가 연산의 결과로, 111 010 011 000이 나왔다.

이 수의 2의 보수는 십진수로 확인해보면 000 101 101 000 = 256 + 64 + 32 + 8 = 360으로, 

(-12) x (30) = -360이 제대로 계산되었음을 알 수 있다.

통신 공부를 시작하려니 뭐가 뭔지 모르겠음 네트워크가 뭔가 패킷이랑 프로토콜은 뭔가 이건 왜하는거고 라우터와 스위치의 차이는 뭐지 하는 나를 위해 쓰는 글 앞으로 풍부하게 채워나가고 수정할 예정

1. 네트워크 (NetWork)

네트워크는 Net와 Work의 합성어로 "컴퓨터간의 통신"을 의미한다. 즉 네트워크로 연결된 컴퓨터는 언제 어디서든 원하는 정보를 공유하여 활용할 수 있다.

네트워크는 다음과 같은 장점이 있다.

1.1. 데이터 공유

A학과 사무실과 B학과 사무실에서 U학교의 학생 정보를 가져와서 신입생에 대한 정보를 명단에 추가한다고 생각해보자. A학과와 B학과는 각각 기존 학생 명단을 받아와 A과 신입생, B과 신입생의 명단을 추가할 것이다. 이때 A학과 사무실은 U학교 학생 명단 + A학과 신입생 명단을 가지고 있을 것이고 B학과 사무실은 U학교 학생 명단 + A학과 신입생 명단을 가지고 있을 것이다. 이 두 명단은 모든 신입생들의 정보를 가지고 있지는 않으므로 온전하다고 할 수 없다. 

이 문제는 학생 명단을 중앙 컴퓨터, 즉 서버에 저장함으로써 해결할 수 있다. 모든 사용자가 공유하며 수정할 수 있는 학생 명단이 있다면 편하지 않을까? 하나의 데이터 파일에 해당하는 마스터 사본을 파일서버(file server)에 저장하고 필요할 때마다 A학과 사무실과 B학과 사무실이 마스터 사본을 수정할 수 있도록 만드는 것이 각자의 컴퓨터에 저장하는 방법보다 더 효율적일 것이다.

그러나 U학교 구성원이 아닌 외부 사람이 학생 명단 데이터에 접근하는 것을 막아야 할 필요가 있을 것이다. 이때는 아래 방법을 사용한다.

• 읽기 전용읽기 전용 : 공유 장치에 저장된 데이터를 읽기만 할 수 있다. 이 권한이 있는 사용자는 데이터를 읽을 수만 있고 수정할 수 없기 때문에 데이터가 변경될 가능성이 없다.
• 읽기/쓰기 : 공유 장치에 저장된 데이터를 읽고 수정할 수 있다. 이 권한이 있는 사용자가 데이터를 수정하면 네트워크에 연결된 모든 사용자는 수정된 데이터를 공유한다.

1.2. 주변장치 공유

A학과 사무실에는 컴퓨터가 3대 있다. 과와 관련한 업무를 효율적으로 처리하려면 세 컴퓨터가 모두 프린트 기능을 사용해야 할 텐데 컴퓨터마다 프린터기를 한 대씩 총 세대 쓰는 것은 비용이 비쌀 것이다. 이럴 때 하나의 프린터기를 각 컴퓨터와 네트워크로 연결해서 공유한다면 비용을 절약하면서도 프린터기를 중앙 집중화할 수 있어 관리도 수월해질 것이다. 

1.3. 능률적인 통신

A, B, C, D, E학과 사무실은 서로 소통을 해야 할 일이 종종 생긴다. 메시지를 전달하기 위해서 각 학과의 사무실마다 네트워크를 연결한다면 간단히 계산해봐도 5! = 120개의 링크가 필요할 것이다. 하지만 우리가 널리 사용하는 데이터 통신 중 하나인 메일을 예로 들어보자. A학과가 D학과로 메시지를 담은 메일을 보내면 이 메일은 메일 서버로 이동하고, 서버는 새로운 메일이 도착했음을 D학과에게 알려줄 것이다. 그러면 D학과는 이메일 프로그램을 이용해 서버에서 메시지를 받아서 확인할 수 있다. 이 경우에는 5개의 사무실이 소통하기 위한 링크가 5개밖에 없을 것이다. 네트워크는 호스트 간의 데이터 송수신을 능률적으로 수행할 수 있도록 해준다.

1.4. 손쉬운 백업

데이터는 귀중한 자산이므로 데이터를 백업하는 일은 매우 중요하다. 네트워크를 이용하면 사용자가 접근 가능한 공유 저장장치 중 하나에 모든 데이터를 손쉽게 백업할 수 있다. 

2. 네트워크의 구성

네트워크에는 세가지 구성요소가 있다. 

2.1. 호스트(host)

호스트는 컴퓨터 네트워크에 연결된 컴퓨터나 기타 장치들을 의미한다. 컴퓨터, 휴대폰, 프린터기에서부터 서버까지 모두 호스트라고 할 수 있다. 우리가 휴대폰으로 카카오톡, 인스타그램 등을 하며 애플리케이션을 사용하는 중 다양한 데이터를 송수신하는데 이는 모두 호스트로부터 출발한다. 

2.2. 네트워크 접속 장치

네트워크 접속 장치는 애플리케이션의 데이터를 정상적으로 전송하기 위한 장치이다. 접속 장치는 다양한 종류가 있지만 기본적으로 스위치와 라우터가 존재한다. 스위치는 한 네트워크 내부에서 데이터를 전송하도록 돕는 장치이고 라우터는 서로 다른 네트워크를 구분 짓고 연결하는 장치이다. 

2.3. 네트워크 전송 매체

호스트와 네트워크 접속 장치는 네트워크 전송 매체에 의해 서로 연결된다. 전송 매체는 크게 유선 전송 매체와 무선 전송 매체로 나뉘는데, 유선 전송 매체는 일반적으로 케이블을 의미한다. 무선 전송 매체는 전파를 말하며, 네트워크 통신에 이용되는 전파는 규격에 따라 전파의 파장이나 주파수가 지정되어 있다. 네트워크에서 데이터를 송신할 때는 전송 매체에 따라 디지털 데이터가 물리적 신호로 변환된다. 

3. 네트워크의 종류

우리가 가까운 거리는 걸어가거나 지하철을 타고 먼 거리는 시외버스나 기차를 타듯이 테이터가 이동하고자 하는 거리에 따라서 네트워크의 종류를 구분할 수 있다. 가장 작은 규모의 네트워크인 PAN(Personal Area Network)부터 광대역 네트워크인 WAN(Wide Area Network)까지 그 쓰임과 네트워크 연결 방법이 다양하다. 지금은 기초를 위해 간단한 것들만 살펴본다.

3.1. LAN (Local Area Network)

LAN은 범위가 지역적인 네트워크로 범위가 건물 안이나 특정 지역인 네트워크이다. 따라서 한 건물 또는 인접한 건물군 내에 있는 네트워크는 하나의 LAN으로 간주된다. 집에서 인터넷을 이용할 때나 PC방, 사무실 등 작은 규모로 인터넷을 연결할 때 LAN을 사용한다. 만약 A학과 사무실과 B학과 사무실이 다른 LAN을 사용하는데 두 연구실 간 데이터 통신이 필요할 때는 두 LAN 간 링크를 만들어야 한다. 각 LAN은 특정한 프로토콜(데이터를 송수신하는 일련의 규칙)로 운용되기 때문에 링크를 만들기 위해서는 서로 다른 네트워크 유형의 데이터 공유 방법을 알아야 한다.

• 신호가 약해지거나 오류가 발생할 확률이 낮다.
• 데이터 전송 비용이 싸다.
• 연결 거리가 짧다.

3.2. WAN (Wide Area Network)

WAN은 2개 이상의 LAN을 넓은 지역에 걸쳐 연결한 것을 말한다. 서로 다른 LAN에 속하는 U학교의 C캠퍼스와 D캠퍼스는 데이터나 프로그램을 공유하기 위해 라우터를 연결하여 WAN을 구성하기도 한다. 추가적으로 LAN에 포함되지 않는 호스트도 WAN을 이용하여 연결될 수 있다. WAN은 ISP(Internet Service Provider)가 제공하는 서비스를 이용해 구축된 네트워크이다. ISP는 인터넷 상용 서비스를 하고 있는 SK, KT 등과 같은 통신 사업자를 의미한다. 

• 멀리 떨어진 LAN을 연결하므로 신호가 약해지거나 오류가 발생할 확률이 높다.
• 데이터 전송 설비를 임대하는 비용이 많이 든다.
• 거리가 멀어지는 만큼 속도가 느려진다.

3.3. 인트라넷 (Intranet)

인터넷에서 사용하는 회선과 여러 기반 기술을 이용하여 구축하는 사설 네트워크이다. 각 지방에 분산된 호스트를 전용 회선으로만 연결하는 것은 어려운 작업이지만 인트라넷을 활용하면 손쉽게 구현할 수 있다. 각 호스트에서 가장 가까운 ISP까지만 연결하면 되기 때문이다. 아무리 호스트가 멀리 떨어져 있어도 호스트를 ISP까지만 연결하면 저렴한 비용으로 사설 네트워크를 구축할 수 있다. 인트라넷을 이용하면 모든 호스트에서 문서관리, 메신저, 게시판, 결제내역 등을 공개되지 않은 웹페이지에서 처리할 수 있다. 예시로는 각 대학교의 포털을 들 수 있다. 

4. 패킷

우리가 매일 사용하는 인터넷은 전 세계의 작은 네트워크부터 큰 네트워크까지 연결된 거대한 연결망이다. 전 세계가 네트워크로 연결되어 있으므로 우리는 해외 웹사이트에 접속할 수 있다. 다만 이를 위해서는 통신에 관한 규칙이 필요한데 이 규칙에는 패킷(packet)이 사용된다. 패킷 구조에 대해서는 앞으로 다른 글에서도 자세히 알아볼 것이다.

패킷은 헤더(header), 페이로드(payload), 제어 요소 등을 포함하는 데이터 세그먼트이다. 헤더는 데이터의 형태와 데이터의 송수신지, 일련번호 등으로 구성되고 페이로드는 실제 전송 데이터를 포함하는 부분이다. 

또한 패킷은 컴퓨터 간에 데이터를 주고받을 때 네트워크를 통해 전송되는 데이터의 전송 단위이다. 만약 용량이 큰 고양이 이미지를 네트워크를 통해 보내고 싶다면 고양이 이미지 데이터를 작게 나누어서 보내는 것이 원칙이다. 만약 용량이 큰 데이터를 그대로 보낸다면 데이터가 네트워크 대역폭을 너무 많이 점유하여 다른 패킷의 흐름을 방해할 위험이 있기 때문이다. 

대역폭(bandwidth) : 네트워크에서 이용 가능한 신호의 최고 주파수와 최저 주파수의 차이로, 데이터를 전송할 수 있는 최대 전송 속도이며 기본 단위는 bps(bit per second)이다. 

송신자가 보낸 패킷은 보낸 순서대로 수신자에게 도착하지 않는다. 따라서 수신자가 예쁜 고양이 이미지를 보기 위해서는 패킷을 원래 순서대로 조립할 필요성이 있다. 그래서 송신 측에서 각 패킷에 순서대로 번호를 붙여 전송하고 수신 측에서는 번호에 맞춰 재조립함으로써 각 패킷을 원래의 위치로 되돌린다. 이렇게 번호 순서로 사진 전체의 패킷을 정렬하면 송신 측에서 보낸 예쁘고 귀여운 고화질의 고양이 사진을 수신 측이 드디어 볼 수 있는 것이다.

출처 : 한빛아카데미 4차 산업혁명과 함께하는 네트워크 개론 (진혜진 지음)