1. 경합 프로토콜
1) CSMA(Carrier Sense Multiple Access)
스테이션이 원할 때마다 전송을 허용하여 신호를 전송하는 다소 무질서한 접근법
□ 스테이션은 전송 전에 매체를 감시
① 아무 활동도 없으면 전송한다.
② 어떤 활동이 있으면 기다린다.
□ 둘 이상 스테이션이 거의 동시 전송하려는 경우 매체가 유휴상태로 감지되면 둘 다 전송하게 돼 충돌이 발생함
□ 다른 스테이션도 이 구간 안에 전송해야 충돌하지만 그 간격이 작으므로 두 번째 스테이션이 그 간격 내에 프레임을 보내게 될 확률도 작다.
2) P－지속(Persistent) CSMA
충돌 횟수를 줄임으로써 효율 향상
□ 매체를 계속 감시하여
① 매체가 유휴상태가 되면 확률 p( 0 ≤ p ≤ 1)로 전송한다.
② 사용 중이면 한 타임 슬롯 (확률 1-p)을 기다린다.
□ 충돌 빈도를 줄이는 방법
① 앞의 전송이 완료될 때 스테이션이 전송하게 될 확률을 더 낮춘다.
② 일반적으로 p 값이 작을수록 충돌이 적어진다.
③ 그러나, 스테이션 수가 늘면 통신량도 늘고, 둘 이상이 동시에 전송할 확률도 늘어나므로 충돌이 문제가 된다.
3) 비－지속(Non－persistent) CSMA
매체를 주기적으로 확인하여 사용 중이면 1 타임슬롯을 기다린다.
□ 두 스테이션이 거의 동시에 유휴 매체를 검출했을 때에만 충돌이 발생한다.
□ 전송 스테이션이 많아지면 충돌도 더 빈번해지고 문제도 더 많아진다.
□ 통신량이 적은 (유휴 상태일 때가 많은) 경우 충분히 적극적이지 못함.
4) 비－지속 CSMA의 성공률
□ G와 함께 증가
① G 값이 크면 알로하 프로토콜이나 지속 프로토콜보다 훨씬 더 좋아진다.
② 예 : G = 9 면 성공률 0.9
슬롯 타임 당 9 프레임을 생성할 때에만 전송에 90%를 사용하지만, 스테이션이 매체를 포화 상태로 만들게 되어 지연이 발생한다.
□ G 값이 작으면 지속 프로토콜이 성공률이 더 높다.
5) CSMA 및 알로하 프로토콜의 성공률
6) 충돌 검출(Collision Detection)
□ 성공률을 높이기 위해 충돌 시간을 줄인다.
□ 주로 CSMA와 함께 사용된다.
□ 낭비되는 시간 : 슬롯 일부 및 경고 신호 전송 시간
7) CSMA/CD
□ 지속 알고리즘들 중 하나와 함께 사용된다.
① 매체가 사용 중이면 지속 알고리즘에 따라 기다린다.
② 매체가 유휴상태이면 그 프레임을 전송하고 감시를 계속한다.
③ 충돌을 감지하면 즉시 전송을 중단, 짧은 경고 신호를 보낸다.
④ 충돌 후 임의의 시간을 기다린 후 다시 전송을 시도한다.
8) 검출이 있는 충돌과 없는 충돌
9) 이진 지수적 백오프(Binary Exponential Backoff)
□ 접근법
① 타임 슬롯 수를 적게 함으로써 과도한 기다림을 최소화
② 두 스테이션이 충돌할 경우 다음 시도에서 성공할 기회는 50%가 된다.
(단, 전송 중인 것이 없다고 가정할 때)
③ 각 충돌 이후에는 슬롯의 수를 늘림으로써 재 충돌할 기회를 지수적으로 감소시킨다.
④ 많은 슬롯만 가능할 때 모든 시도가 실패한 경우이므로 오랜 기다림만이 유일한 해결책이다.
10) 토큰 링 네트워크
PC를 전선이나 광섬유 매체로 원형으로 연결한다.
11) 토큰 패싱 : 프레임 교환
□ 전송 : 스테이션이 토큰을 받았을 때
① 전송을 원하는 경우, 데이터와 목적지 주소를 토큰에 삽입하고 제어 비트를 변경한다.(데이터 있음을 표시)
② 전송할 것이 없는 경우, 토큰을 이웃으로 패스한다.
□ 수신 : 제어 비트를 조사한다.
① 아무 것도 없으면 이웃으로 패스한다.
② 데이터가 있으면 목적지 주소를 조사하여
→ 다른 곳으로 가는 것이면 이웃으로 발송한다.
→ 자신의 것이면 데이터를 복사하여 PC로 전송한 다음 그 프레임을 링에 도로 올린다.
□ 전송 프레임의 제거
→ 당초에 송신했던 스테이션으로 되돌아오면 그 프레임을 제거한 뒤 다시 링 위에 올린다.
□ 단점 : 한 스테이션이 매체 독차지할 수 있다.
12) 슬롯 링(Slotted Ring)
□ 토큰 링, 케임브리지(Cambridge) 링이라고 한다.
□ 전송용 프로토콜 토큰이 여러 개 인 점을 제외하면토큰 링과 유사하다.
□ 장거리 링에 더 적합하다.
□ 장점 : 새 스테이션 토큰을 더 많이 차지할 수 있다.
□ 단점
① 한 스테이션이 토큰을 더 많이 차지할 수 있다.
② 인접 스테이션 간의 링크가 깨지면 네트워크 다운 초래.
③ 토큰을 전송하는 중에 NIC가 오 동작하면 불완전하고 유효하지 않은 토큰이 링을 순회하게 된다.
13) 토큰 버스(Token Bus)
□ 물리적으로는 공통버스와 유사하나 토큰 링과 유사한 원리를 사용하여 통신한다.
□ 응용 분야 : 조립 라인, 공장 자동화 환경
□ 토큰 패싱 : 번호 순 (논리적으로 번호를 부여한다)
① 단, 번호가 제일 큰 스테이션은 번호가 제일 낮은 스테이션으로 토큰을 패스한다.
② 전송 방향 : 물리적으로 어느 방향이나 가능하다.
③ 버스 인터페이스 : 프레임의 주소를 조사하여 자신에게 온 프레임을 읽는다.
④ 공통 버스 구조 : 조립 라인을 따라 배치된 장치들을 컴퓨터로 제어가능
□ 문제점 : 새 스테이션의 추가 및 삭제가 어렵다.
14) 경합 프로토콜의 요약
2. 데이터 압축
1) 데이터 압축
□ 시간적 중복성 (temporal redundancy)
→ 시간의 흐름에 따라 같은 데이터가 중복되어 나타난다.
□ 공간적 중복성 (spatial redundancy)
→ 공간 상의 여러 위치에 같은 데이터가 중복되어 나타난다.
□ 복원 (Decompression)시의 정보에 따라
→ 손실(loss) 기법
→ 무손실(lossless) 기법 : 복원 결과와 원래 데이터가 동일하다.
□ 압축 속도와 복원 속도에 따라
→ 대칭 기법
→ 비 대칭 기법
2) 허프만 코드(Huffman Code)
□ 빈도 의존 코드(Frequency dependent code)
→ 출현 빈도가 높은 문자일수록 비트 수를 적게 할당하여 부호화한다.
□ 전위문자 특성 (Prefix Property)
→ 어떤 문자 코드가 결코 다른 문자 선두에 나타나지 않는다.
3) 허프만 알고리즘
□ 각 문자에 대한 이진 목을 만든다.
→ 각 트리에 대해 트리의 가중치 (문자의 빈도)를 할당한다.
□ 가장 작은 가중치를 가진 트리를 찾는다.
① 선택된 2개를 좌우 노드로 하는, 새 노드를 가진 트리로 합병
② 두 개 이상 있으면 임의로 선택한다.
□ 한 개의 트리만 남을 때까지 앞의 단계를 반복한다.
□ 완성 시 원래의 각 노드는 마지막 이진 목의 잎이 된다.
□ 어느 이진 목에서나 루트에서 잎까지 경로는 유일하다.
□ 왼쪽 자식 포인터엔 ‘0’, 우측 자식들엔 ‘1’을 각기 할당
4) 허프만 코드의 예
평균 부호 길이 : 2.25 비트
→ 고정-길이 부호화 시 : 3 비트
□ 허프만 코드 : 메시지 수신과 해석
5) 허프만 트리들의 합병
6) 런 길이 부호화
□ 연속적으로 반복되는 단위 정보 (문자, 픽셀)들을 그 정보 및 반복된 횟수로 표현한다.
→ Run : 같은 비트나 문자의 연속
□ 같은 비트의 런
→ 단지 런 길이(고정 길이의 2진 정수)만 전송한다.
→ 수신측 은 각 길이들을 받아 사이에 다른 비트를 삽입하여 런 길이만큼의 비트를 생성한다.
→ 팩스 전송에 유용하다 : “0” 이나 “1”의 런을 찾아 그 길이만 전송한다.
□ 다른 문자들로 된 런
→ 문자를 런 길이 뒤에 붙여 보낸다.
□ 런 길이 부호화 : 각종 문자의 런
① 예1
원문 “AAAAAAABCCCC” (12 bytes)
압축 후 “A!7 BC!4” ( 7 bytes)
② 예2
원문 “TABBBBBBBBBBBBBBBBBBCGLM” (24 bytes)
압축 후 "TAB@18CGLM" (10 bytes)
7) 런 길이 부호화의 예
8) 상대적 부호화
□ 차분 부호화 (Differential Encoding)라고도 한다.
□ 원리
① 첫 프레임이 전송되어 수신 측의 버퍼에 저장된다.
② 송신측은 둘째 프레임을 첫 프레임과 비교하여 그 차이를 부호화하여 프레임 형식으로 전송한다.
③ 송신측은 이를 받아 먼저 받은 프레임에 그 차이를 적용하여 둘째 프레임을 만든다.
④ 둘째 프레임을 버퍼에 저장하고 각기 새 프레임에 대한 처리를 계속한다.
□ 상대적 부호화의 예
9) Lempel－Ziv 부호화
□ 사전－기반 압축 알고리즘
□ 원리
① 자주 반복되는 문자열을 찾아 처음에 한 번만 저장하고, 그 이후에는 해당 코드로 대치해 준다.
② 방법 1 : 문자열에 따라 어떤 특수 문자로 대치한다.
③ 방법 2 : 사전에 등록해 둔 다음, 이후에 발생한 때는 포인터를 나타내는 값으로 대치한다.
□ 응용 예
① 파일 압축 프로그램
→ Unix의 압축 지령 ‘compress’
→ ‘pkzip’, DOS의 ‘ARC’ 유틸리티
② V.42bis 압축 모뎀 표준
10) 영상 압축
□ 압축 알고리즘 없다면 멀티미디어의 실현이 어렵다.
① 화소 (picture element, pel), 픽셀 (pixel)
② 영상 데이터 : 640×480×24bit = 7,372,000 비트
□ 영상 표현
① 색상 증가(고 해상도)에 따라 복잡해진다.
② 비디오 이미지 : 3개의 8비트 그룹으로 표현
③ RGB, YUV, YIQ, YCrCb, (출판 분야 : 4가지, YMCK)
□ YIQ
① NTSC 에서 밝기와 색상 표현을 위해 사용
② 밝기(luminance) 한 그룹, 색상(chrominance) 두 그룹
③ RGB ? YIQ 변환
Y = 0.30R - 0.59G + 0.11B
I = 0.60R - 0.28G + 0.32B
Q = 0.21R - 0.52G + 0.31B
11) JPEG
□ Joint Photographic Experts Group
① ISO, ITU와 IEC의 공동 노력으로 만듬
② 회색계 (gray scale)와 사진 수준 컬러 영상의 압축 표준
③ 손실 압축 (lossy compression)
□ JPEG 압축 단계
① 이산 코사인 변환(DCT, discrete cosine transform) 단계
② 양자화 (quantization) 단계 : 양자화 표는 규정 안 함
③ 부호화 (encoding) 단계
12) DCT(Discrete Cosine Transform)
□ 영상을 8x8 픽셀 블럭으로 나눈다.
□ 각 8x8 픽셀 블록 T[i][j]에 대해 2차원 DCT를 한다.
□ T : 공간 주파수 (spatial frequencies) 값들의 집합
□ DC 계수 : T[0][0]의 값
→배열 내 값들의 평균 값 (i=0일 때 코사인 함수 값은 1)
□ AC 계수 : T 안의 나머지 값들
8×8 픽셀 블록으로 나눈 640×480 VGA 화면 이미지
12) DCT(Discrete Cosine Transform)
8×8 픽셀 블록으로 나눈 640×480 VGA 화면 이미지
13) IDCT
역 DCT (Inverse DCT)
→ 공간 주파수를 원래의 픽셀 값으로 복원한다.
14) 양자화(Quantization) 단계
DCT 변환 블록에 대해 양자화를 한다
→Q[i][j] = Round(T[i][j]/U[i][j]) ; i =0,1, …, 7
15) 부호화(Encoding) 단계
□ 데이터 압축에 적절한 형태로 변환한다.
→Zig-zag scan : Q의 2차원 데이터를 선형화
□ 압축한다.
→수정 Huffman 부호화
16) MPEG(Moving Pictures Expert Group)
① ISO, IEC, ITU 공동 작품
② 비디오 압축 표준
③ MPEG-1 : CD-ROM 수준 비디오, 초기 위성 방송 시스템용
④ MPEG-2 : 멀티미디어 오락, HDTV 등
⑤ MPEG-4 : 저 대역 채널 상의 원격 회의용 (진행 중)
□ NTSC 비디오 표준 : 30 fps (frame per second)
□ 프레임간 시간적 중복성 (redundancy) 제거
□ MPEG 비디오, MPEG 오디오, MPEG 시스템
17) MPEG : 프레임 유형
□ I 프레임 (intrapicture frame)
① 독립적인 프레임
② JPEG 부호화 영상
□ P 프레임 (predicted frame)
① 이전 프레임과 다음 프레임간의 차이를 부호화
② 움직임 보상 예측 기법을 사용 (H.261)
□ B 프레임 (bi-directional frame)
양 방향 예측
□ 전형적인 MPEG 프레임 시퀀스
18) P 프레임의 부호화
□ 3 개의 매크로 블록 : 16x16 픽셀 블록
① 광도 (luminance) 1개
② 색도 (chrominance) 2개 : 8x8 로 감소 Y : U : V = 4 : 1 : 1
□ 움직임 보상 예측
① 최적 부합 (matching) 블럭을 조사한다.: 각 매크로 블록을 조사하여 첫 I 프레임에 가장 잘 부합하는 매크로 블록을 찾는다.
② 움직임 벡터 (motion vector)를 구한다. : 부합하는 매크로 블록 간의 차이 : 픽셀의 변위를 x, y로 계산
③ 프레임 내 모든 매크로 블록에 대해 같은 작업을 행한다.
□ 보간 (interpolation)
① 2의 실제 값을 토대로 1개의 값을 예측하는 방법
② 매크로 블록 부합(matching)을 위해, 계산된 차이와 움직임 벡터를 이용하
여 과거와 미래의 프레임을 탐색한다.
□ 움직임 벡터를 보간, I 프레임과 P 프레임 사이에 있는 현 프레임(B 프레임)에서 잘 부합되는 매크로 블록의 위치를 예측하여 구한다.
□ 보간을 이용한 값 예측
19) 압축 기법 요약
[정리하기]
1. 네트워크에서 둘 이상의 사용자가 동시에 송신하고자 할 때 통신 경로상에서 어느 데이터가 먼저 전송되어야 하는지를 결정하지 못하는 것을 경합이라 하며, 이러한 경합을 해결하기위한 프로토콜로는 CSMA, CSMA/CD 등이 있으며, 토큰을 이용하여 경합을 해결하는 프로토콜로는 토큰 링, 슬롯 링, 토큰 버스 방식이 있다.
2. 데이터 통신시 보내고자 하는 데이터의 양을 줄임으로써 전송되는 데이터의 속도를 높이는 방법을 데이터 압축이라 하며, 이러한 데이터 압축의 방법으로는 허프만 알고리즘, 런 길이 부호화, 상대적 부호화, Lempel－Zip 알고리즘 등이 있다.
3. 영상 데이터의 전송에 사용되는 데이터 압축 기법으로는 MPEG과 JPEG 등이 있다.
4. 참조
① http://dogm.net/DataCompression/
② http://www.mpeg.org/MPEG/index.html
③ http://vision.hanyang.ac.kr/research/the_others/Mpeg/Mpeg.html
④ http://www.ora.com/catalog/webphoto/chapter/ch06.html
