데이터통신 10.2 블록 코딩

블록코딩에서는 데이터워드(dataword)라고 불리는 k비트의 블록으로 메시지를 나눈다. 각 블록의 r개의 중복 비트들을 더하여 길이 

n= K+r이 되도록 한다. 

결과로 얻는 n비트 블록은 코드워드(codeword)라고 불린다. 

구하는법 -> 일련의 각각 k비트로 된 데이터워드와 n비트로된 코드워드를 갖는다는 것을 아는게 중요하다.

k개 비트를 이용하여 2^k개의 데이터워드를 만들 수 있고, n개 비트를 사용해서는 2^n개의 코드워드를 만들 수 있다.

n>k이므로 (n=k+r) 가능한 코드워드의 개수 > 가능한 데이터워드의 개수. 

블록코딩기법은 일대 일이다. 즉, 동일한 데이터워드는 동일한 코드워드로 부호화된다. 이는 2^n-2^k개의 코드워드는 사용되지 않는다는 것을 뜻한다. 나머지 코드워드를 무효 또는 불법적인 것이라고 말한다. 

수신자가 인식불가능한 코드워드를 수신한다는 것은 데이터가 전송되는동안 오류가 발생되었다는 것을 나타낸다.

 

 

10.2.1 오류 검출

블록코딩을 사용하여 어떻게 오류를 찾아낼 수 있을까?

코드워드가 바뀐걸 알수있는 두가지 조건

1. 수신자는 유효 코드워드를 찾아내거나, 그 리스트를 가지고 있다.

2. 원래의 코드워드가 무효 코드워드로 바뀌었다.

이런경우를 생각해보자.

데이터워드      코드워드

00                 000

01                  011

10                  101

11                   110

숫자 두개가 같으면 뒤에 0붙고 다르면 뒤에 1붙은경우, 

1.수신자가 011을 수신했다면 유효코드이기 때문에 수신자는 데이터워드 01을 추출한다.

2.코드워드가 전송도중 손상되어 111이 수신되었다. (원래 110이여야함) 이는 유효코드가 아니므로 버려진다.

3. 코드워드가 전송도중 손상되어 000이 수신되었다.(만약 011인데 두비트가 깨져서 000이 수신)되었다면 유효코드이므로 부정확한 데이터워드 00을 추출한다 --> 오류를 찾지 못하는 형태.

 

 

해밍거리

오류제어의 중심 개념중 하나는 해밍거리(hamming distance)이다. 두 같은 크기의 워드사이의 해밍거리는, 서로 차이가 나는 해당 비트들의 개수이다. 이제부터 두 워드 x와 y사이의 해밍거리를 d(x,y)라고 표시한다.

해밍거리가 오류 검출에서 중요한 이유 : 수신된 코드워드와 발신된 코드워드 사이의 해밍거리는 전송되는동안 오류가 생긴 비트들의 수.

ex)코드워드 00000이 발신되고 01101이 수신되었다고 해보자. =3개의 비트에 오류가 발생한 것. 둘 사이의 해밍거리는 

d(00000,01101) = 3이다. 만약 발신되고 수신된 코드워드 사이의 해밍거리가 0이 아니면, 코드워드가 전송되는 동안에 오류가 발생하는 것이다. 

 

 

오류검출을 위한 최소 해밍거리

코드워드의 집합에서, 최소 해밍거리(minimum Hamming distance)는 모든 가능한 코드워드 쌍들 사이의 가장 작은 해밍거리이다.

s개의 오류를 검출하기 위한 최소 해밍거리는, 전송도중 s개의 오류가 발생한다면, 송신된 코드와 수신된 코드사이의 해밍거리는 s이다. 

우리의 코드가 s개의 오류를 검출해내기 위해서는 최소 해밍거리가 s+1이 되어야 하는데, 이는 손상된채로 수신된 코드가 유효코드중의 하나가 될 수 없게 하기 위해서이다.

코드워드끼리의 해밍거리가 3이라고 하면, 최대 2개의 오류까지만 검출이 가능합니다.

 

 

선형블록코드

오늘날 사용되는 대부분의 블록코드는 선형 블록 코드(linear block code)중 하나이다. 비선형블록코드는 오류검출이나 정정에 널리 쓰이지 않는데, 그 구조가 이론적으로 복잡하고 구현하기 힘들기 때문이다.

선형블록코드는 너무너무 어렵다. 간단히 알려준다 이책에서는.

두 유효한 코드워드에 대해 XOR연산을 가하면 다른 유효한 코드워드가 생성되는 코드.

 

선형 블록코드의 최소 해밍거리는 쉽게 알 수 있다. 최소 해밍거리는 0이 아닌 가장 적은수의 1을 가지고 있는 코드워드의 1의 개수이다. 

000 101 011 110 이라면 최소 해밍거리는 2이다. 

 

 

패리티 검사코드

pairty-check code

는 선형블록코드이다. 이 코드는 k 비트 데이터워드를 n=k+1 이 되도록 n비트 코드워드로 바꾸는 것이다. 

추가된 비트는 패리티 비트(pairty bit)라고 불리며, 전체 코드워드의 1의 개수가 짝수가 되도록 선정된다. (홀수인 경우도 있다)

이 범주에서의 최소 해밍거리는 2이다. = 코드가 단일비트 오류 검출코드라는 것을 의미.

 

부호화기는 4비트 데이터워드 a0, a1, a2,a3의 사본을 받아 패리티비트 r0을 생성한다. 

데이터워드와 패리티비트는 5비트 코드워드를 만들어낸다. 

추가된 패리티비트는 전체 코드워드의 1의 개수를 짝수로 만든다. 

 

송신자는 전송도중 손상된 코드워드를 보낼 수 있다. 수신자는 5비트 워드를 받는다. 수신자 쪽의 확인기가 한가지만 예외일 뿐, 송신자쪽의 생성기와 동일한 일을 한다. 5개의 비트를 다 더해 모듈로 -2 연산을 한거를 신드롬이라고한다.

수신된 워드의 1의 개수가 짝수이면 신드롬은 0이고, 아니면 1이다.

신드롬이 0이라면, 수신된코드에는 오류가 없는것, 신드롬이 1이면 데이터부위를 버리게된다.

->단순 패리티검사 코드는 홀수개의 오류를 검출한다.