10장. 오류 제어와 흐름 제어

오류 검출(Error Detection)

송신측에서 보내고자 하는 원래의 정보 이외에 별도로 잉여분의 데이터를 추가

수신측에서는 이 잉여(Redundancy) 데이터를 검사함으로써 오류검출이 가능

 

종류

패리티 검사, 블록 합 검사, CRC(Cyclic Redundancy Check), Checksum 등

 

패리티 검사

한 블록의 데이터 끝에 한 비트 추가

종류
짝수 패리티 : 1의 전체 개수가 짝수개
홀수 패리티 : 1의 전체 개수가 홀수개

 

동작과정

송신측
짝수 또는 홀수 패리티의 협의에 따라 패리티 비트 생성
ASCII 문자(7bit) + 패리티 비트(1bit) 전송

수신측
1의 개수를 세어 오류 유무 판단(짝수 또는 홀수)
맞지 않다면 재전송 요청

 

단점
짝수개의 오류는 검출 불가
예) 11011001 : 짝수개의 오류가 발생하여 1의 개수가 홀수인 경우

 

블록 합 검사

이차원 패리티 검사 : 가로와 세로로 두 번 관찰

검사의 복잡도를 증가  : 다중 비트 오류와 집단 오류(Burst error)를 검출할 가능성을 높임

 

동작과정
데이터를 일정크기의 블록으로 묶음
각 블록을 배열의 열로 보고 패리티 비트를 계산하여 추가
각 블록의 행에 대한 패리티 비트를 계산하여 추가한 후 전송

예시
전송하고자 하는 데이터

1100111 1011101 0111001 0101001
각 열(Column) 비트의 1의 개수를 합해 짝수 혹은 홀수 중 하나의 패리티
비트 줌(여기선 짝수)
두 번째 비트들이 더해지고 패리티 비트가 얻어짐
블록 합의 마지막 비트는 블록 합 데이터 단위 자체를 위한 패리티 비트
이고 블록 내의 모든 패리티 비트들을 위한 비트임

 

단점
두 번째 블록과 마지막 블록의 동일 위치에 각 두 개의 오류발생
하나의 블록에서 두 개에 오류가 생기고, 다른 블록의 동일한 위치에서 두 개의 오류가 발생한 경우 검출 불가

 

CRC

전체 블록검사
이진 나눗셈을 기반

계산 방법

메시지는 하나의 긴 2진수로 간주
특정한 이진 소수에 의해 나누어짐
나머지는 송신되는 프레임에 첨부 나머지를 BCC(Block Check Character) 라고도 함
프레임이 수신되면 수신기는 같은 제수(generator)를 사용하여 나눗셈의 나머지 를 검사
나머지가 0이 아니면 오류가 발생했음을 의미

 

부호화 과정
각 비트들의 값을 보면서 하나의 함수를 만드는 과정
정보 비트를 전송비트의 다항식에 의한 표현으로 변환

캐리(Carry)가 없는 Modulo-2 연산 

 

전송 하고자 하는 데이터 : 10001101
원하는 BCC 비트의 길이 : n
제수의 길이 : n+1 

연산과정
전송하고자 하는 데이터 뒤쪽에 n개의 0을 삽입
제수로 나눔
데이터 뒤의 n개의 0을 R로 대체
전송

 

오류 검출 방법
수신된 데이터를 송신측과 합의된 제수로 나눔
연산결과 나머지가 0이면 오류 없음
그렇지 않다면 재전송 요청

 

하드웨어로 구성된 CRC
계산된 BCC는 쉬프트레지스터(Shift register)에 축적
이 레지스터의 구성은 CRC 코드를 생성
레지스터 중에 있는 각 구분은 생성다항식의 등급과 동일
Exclusive-OR요소들의 수도 또한 그 다항식과 관계되는 수
종류
-CRC-16
-CRC-32
-CRC-CCITT 등

 

CRC-16
8비트 캐릭터용의 동기방식에 응용
BCC축적은 16비트
생성다항식 : x16+x15+x2+1
검출능력
-집단오류검출은 최대 16비트 길이까지 가능
-오류의 집단이 16비트보다 큰 경우는 99%이상의 확률

 

CRC-CCITT

유럽시스템들의 표준 BCC
8비트 캐릭터로 조작하는 경우는 BCC축적은 16비트

 

Checksum

전송 데이터의 맨 마지막에 앞서 보낸 모든 데이터를 다 합한 합계를 보수화하여 전송
수신측에서는 모든 수를 합산하여 검사하는 방법

 

동작과정 - 송신측
데이터 단위를 n(보통은 16) 비트의 여러 세그먼트로 나눔
이 세그먼트들은 전체 길이도 또한 n비트가 되도록 1의 보수 연산을 이용하여 합산
전체 합은 보수화되고 원래 데이터 단위의 끝에 삽입
이렇게 확장된 데이터 단위는 네트워크를 통해 전송

동작과정 - 수신측
검사 합을 포함하여 모든 세그먼트들을 더했을 때 모든 비트가 1이 나오지 않으면 오류
송신측에서 검사 합을 최종 삽입할 때 1의 보수를 삽입하기 때문에 원래의 세그먼트들의 합을 더해주면 1이 되기 때문

 

송신측
전송하고자 하는 데이터 : (11100101, 01100110, 11100110)

최종 데이터 (11100101, 01100110, 11100110, 11001110)

 

 

송신측
수신된 데이터 : (11100101, 01100110, 11100110, 11001110)

최종 합은 1이며, 오류 없음

 

오류복구

Stop-and-Wait ARQ

송신측이 하나의 프레임을 전송
수신측에서는 해당 프레임의 오류유무를 판단
오류가 없을 경우 송신측에게 ACK를 전송
오류가 있는 경우 NAK를 전송하여 재전송 유도

 

특징
흐름제어 방식 중에 가장 간단한 형태
한 개의 연속적인 블록이나 프레임으로 메시지를 전송할 때 효율적
전송되는 프레임의 수가 한 개이므로 송신측이 기다리는 시간이 길어져 전송효율 저하
한번에 한 개의 프레임만 전송
송ㆍ수신측 간의 거리가 멀수록 각 프레임 사이에서 응답을 기다리는 데에 낭비되는 시간 때문에 효율 저하

 

동작 과정
송신측은 데이터 전송 후 ACK, NAK를 받을 때 까지 대기
오류가 없으면 ACK를 송신
수신측은 수신 프레임에 대하여 오류검사를 수행
오류가 있으면 NAK를 송신
송신측에서는 NAK를 수신할 경우 프레임을 재전송

 

Go-Back-N ARQ

연속적 ARQ(continuous ARQ)
수신응답 대기의 오버헤드 감소

 

특징
프레임의 수신은 순차적
포괄적 수신확인
오류 발생 프레임 부터 모두 재전송

프레임에 순서번호를 삽입

 

 

Selective Repeat

연속적 ARQ
오류가 발생한 프레임만 재전송

특징
송신측과 수신측은 동일한 크기의 Sliding-window를 보유
각각의 프레임에 대한 수신확인을 수행

수신측은 프레임의 순서에 상관없이 수신

 

 

전진오류 정정

단일 비트 오류 정정

오류가 발생한 위치를 알아야 함
7비트 데이터의 단일 비트 오류 정정을 위해서는 8가지의 상이한 상태를
구별할 패리티 비트가 필요

 

해밍코드

연산방법
1의 값을 가진 비트의 위치값을 이진수로 Exclusive-OR한다.

 

최종형태 (전송)

수신측 오류 검출 및 정정 방법
오류가 없는 경우
−수신한 데이터내의 1의 값을 갖는 비트의 위치값을 계산

수신측 오류 검출 및 정정 방법
오류가 발생한 경우
−수신 프레임

결과가 1011 이 나왔고, 십진수로 변환하면 11이라는 값이 나오므로 11번째 비트에 오류 발생
오류정정 : 비트값이므로 0은 1로, 1은 0으로 변환

 

 

상승코드

길쌈코드(길쌈부호)
IS-95(CDMA)나 IMT-2000과 같은 이동통신에서 주로 사용

현재의 입력이 과거의 입력에 대하여 영향을 받아 부호화되는 방법 
비블록화 코드

 

응용 기술
바이터비 코드(Viterbi code)
터보 코드(Turbo code)

 

구성 요소
쉬프트 레지스터(shift register) : 정보를 암호화할 때 사용되는 일종의 기억장치
생성다항식 : 쉬프트 레지스터와 결과 값을 연결할 때 사용(XOR)

출력

원시비트들을 쉬프트 레지스터에 통과시킴
modulo-2 가산기를 사용하여 전송비트 생성

 

동작과정
1최초의 모든 쉬프트 레지스터는 0으로 설정
각 입력 측으로부터 한 비트씩 쉬프트 레지스터로 삽입
가산기는 쉬프트 레지스터의 값들을 modulo-2연산을 통하여 계산
멀티플렉싱 스위치는 가산기의 값을 차례로 하나씩 취함
멀티플렉싱 스위치에서 취한 값들을 나열한 것이 출력 값
전송

 

디코딩

경계값(Threshold) 디코딩
짧은 코드
적은 수의 오류 포함

순차적(sequential) 디코딩
Wozencraft에 의해 발명
오류제어 방법 강력
회로의 복잡도 증가
FEC응용의 주류로 기대

 

오류 복구 및 정정 기법의 응용

ARQ가 적절한 응용

주기적으로 인터럽트가 가능한 형식으로 전송하는 데이터의 전송응용
FEC에 비해 경량
신속한 전송 가능

 

응용분야

종이 혹은 자기테이프장치는 전송된 메시지의 사본을 만들 수 있어 ARQ에 적합
ARQ의 응용에서는 어떤 코드의 검출능력이 실질적으로 그것의 수정 능력 보다 더 커야 한다. 즉 코드의 잉여도가 크지 않으면 ARQ기법이 FEC보다 유리
오류가 집단적으로 사용되는 경우 ARQ는 데이터 자체에 대한 재전송을 요 청하기 때문에 오류의 수와는 직접적인 상관관계가 없어 적절
평균 비트 오류율이 현저하게 줄어든 현재의 네트워크에서는 경량의 ARQ가 FEC보다 적합
간단한 패리티검사코드는 그 경제성으로 인하여 리얼타임 폴링에 사용

 

FEC가 적절한 응용

송수신측 사이에 인터럽트를 받지 않는 연속적인 형태로 데이터가 교환되는 응용에 적합
터미널이 버퍼가 없어도 됨

 

응용분야
역 채널이 ARQ에 만족할 만한 사항이 아닐 경우
채널의 전파지연시간이 너무 길어 Stop-and-Wait ARQ가 부적합한 경우에 적절

4800bps이상 속도의 시분할 멀티플랙서들 사이에서의 전이중방식 전송은
데이터 전송과정에서의 인터럽트가 정상적으로는 허용될 수 없으므로 FEC의 사용이 적합

 

 

ARQ나 FEC 어느 것이나 이용될 수 있는 응용

ARQ와 FEC의 설치에 필요한 모든 특성들이 만족되어야 함
FEC는 특별한 채널이나 터미널기기의 특성에 대한 요구사항이 더 적음
FEC를 선택하지 않는 주요한 이유는 기기에 소요되는 경비와 허용 가능한 오류율 등과 같은 사용자의 목적이나 또는 요구조건 때문
ARQ가 선택되지 않는 주요 이유는 채널이나 터미널장비의 제약

 

 

흐름 제어

정의

송신기가 확인 응답을 기다리기 전에 보낼 수 있는 데이터의 양을
제한시키기 위해 사용되는 기법

 

목적

버퍼의 오버플로우(overflow)로 인한 데이터의 손실방지
네트워크 자원을 낭비하는 재전송 방지

 

Xon/Xoff

컴퓨터와 주변기기간의 비동기 통신 제어에 사용되는 프로토콜
모뎀에서 데이터의 흐름제어를 위해 사용

특징
컴퓨터와 주변기기간의 상이한 전송속도로 인해 발생되는 통신상의
문제를 해결
부호화된 문자로 비트통신에서 인식되지 않을 가능성
수신측이 송신측의 데이터 송신을 제어

 

동작과정
컴퓨터는 프린터에게 출력할 데이터를 전송
컴퓨터가 보내는 속도보다 프린터가 출력하는 속도가 느리기 때문에 프린터는 버퍼가 꽉 차게 되면 Xoff 를 보내어 컴퓨터의 송신을 잠시 멈춤
버퍼에 여유가 생기면 프린터는 다시 컴퓨터에게 송신 하라는 Xon을 전송
컴퓨터는 데이터를 계속해서 송신
이러한 과정이 컴퓨터가 데이터를 모두 송신할 때 까지 계속

 

RTS/CTS

RS-232C에 사용
모뎀을 이용한 통신에서 상이한 보오율을 조정

산업용 네트워크에서 사용

특징
충돌방지를 위해 상호간 전송예비신호 전송
특정 핀을 이용하여 원하는 신호 전달

 

동작과정
A는 보내고자 하는 데이터가 있을 때 4번 핀을 이용하여 RTS신호 set(raising:1)
B는 이에 받을 준비가 되었다는 CTS를 5번 핀을 set(raising:1)
A는 응답을 받고, 2번 핀을 이용하여 실제 데이터를 전송

이때 B측이 데이터를 더 이상 받지 않기를 원하면 5번 핀을 reset(lowering:0)
A는 이를 알아채고 데이터 송신 중단

 

Slding-window(연속적 ARQ)

송신측의 송신된 하나의 프레임과 수신측의 수신확인 프레임간의 1:1대응 방식을 탈피
송수신측에 버퍼를 이용한 전송방식
수신측의 응답방식은 포괄적 수신확인 허용

특징
수신측으로부터 응답 메시지가 없더라도 미리 약속한 윈도우의 크기만큼 의 데이터 프레임을 전송
송수신 윈도우 사이즈 동일
수신측에서는 확인 메시지를 이용하여 송신측 윈도우의 크기를 조절, 전송속도 제한

 

동작과정
최대 윈도우 크기 : 7(0~7)
빗금 친 부분
−송신측 : 전송 가능 범위
−수신측 : 수신 가능 범위