• 데이터 링크 계층에서 "오류(error)"의 정의: 전송된 데이터가 원래의 데이터와 일치하지 않거나, 전송 중 손실되거나 왜곡되는 것을 의미합니다.
• 발신자가 0 비트를 전송 - 수신자는 발신자가 1 비트를 전송했다고 생각하거나 - 수신자는 어떤 비트가 전송되었는지 알아낼 수 없습니다.
• 발신자가 1 비트를 전송 - 수신자는 발신자가 0 비트를 전송했다고 생각하거나 - 수신자는 어떤 비트가 전송되었는지 알아낼 수 없습니다.

데이터 통신에서, 오류 감지(Error Detection)는 데이터 전송 중에 어떤 오류가 발생했는지를 확인하는 과정을 말합니다. 그러나 이 방법은 오류를 수정하는 것은 아니며, 오류가 발생했을 뿐 어떤 식으로든 오류를 수정하지는 않습니다.

반면, 오류 수정(Error Correction)은 오류를 감지하는 것과 마찬가지로 오류를 발견하지만, 오류가 발생했다는 사실뿐만 아니라 오류를 수정할 수 있는 방법을 알고 있습니다. 따라서 오류 수정 기술은 오류를 검출하고 수정하여 데이터 통신의 신뢰성과 안정성을 높이는 데 매우 유용합니다.

데이터 통신에서 오류를 감지하는 일반적인 방법 중 하나는, 원래의 데이터에 추가적인 비트를 추가하여 오류를 감지하는 방법입니다. 이러한 비트를 오류 검사 비트(Error Checking Bits) 또는 패리티 비트(Parity Bits)라고 합니다.

패리티 비트는 원래의 데이터 비트에서 1의 개수를 세어 그 결과를 홀수 또는 짝수로 만들어서 추가됩니다. 이렇게 함으로써, 데이터가 전송되는 동안 데이터의 변화나 손상이 발생할 경우, 수신자는 패리티 비트를 검사하여 오류를 감지할 수 있습니다.

그러나 이 방법은 모든 종류의 오류를 검출할 수 있는 것은 아니며, 일부 오류는 검출하지 못할 수 있습니다. 따라서 보다 안전한 방법으로는 순환 중복 검사(Cyclic Redundancy Check, CRC)와 같은 오류 검출 기술을 사용할 수 있습니다.

물리 계층에서는 연속된 0을 피하기 위해 블록 부호화(Block Coding)가 사용됩니다. 이를 통해 데이터 전송 시 0이 연속적으로 나타날 때 발생할 수 있는 문제를 방지할 수 있습니다.

또한, 블록 부호화는 데이터 전송 중 발생하는 오류를 검출하고 수정하는 오류 검출 및 수정 기술로도 사용됩니다. 이러한 방식으로 블록 부호화를 사용하면, 전송되는 데이터 블록에 추가된 검사 비트를 통해 수신자가 오류를 검출하고 수정할 수 있습니다.

오류 검출 및 수정 기술 중 하나인 해밍 부호(Hamming Code)는 블록 부호화를 사용하여 오류 검출 및 수정을 수행하는 대표적인 방법 중 하나입니다. 해밍 부호는 데이터 블록의 비트 수에 따라 검사 비트를 추가하여 오류를 검출하고 수정할 수 있습니다.

데이터워드(Dataword)는 원래의 메시지를 나타내는 블록입니다. 이것은 전송하려는 정보를 나타내며, 일반적으로 k 비트로 구성됩니다.

코드워드(Codeword)는 블록 부호화(Block Coding)을 적용하여 생성된 메시지 블록입니다. 이것은 오류 검출 및 수정을 위해 데이터워드에 추가된 검사 비트를 포함하며, 일반적으로 n 비트로 구성됩니다.

데이터워드로부터 n 비트의 코드워드를 생성하기 위해서는 데이터워드에 추가적인 비트를 추가해야 합니다. 이 추가 비트는 데이터워드에 더해진 검사 비트로, 데이터워드에 있는 정보 비트와 함께 전송되어 오류 검출 및 수정을 가능하게 합니다. 이 때, 검사 비트의 개수는 r로 표현되며, r = n - k입니다. 즉, 추가적인 r 비트가 코드워드에 추가됨으로써 데이터워드를 n 비트의 코드워드로 변환합니다.

다음은 블록 부호화를 적용하여 메시지를 부호화하는 표입니다.

Message	Encoded Message
00	0000
01	0101
10	1010
11	1111

• k는 데이터워드(Dataword)의 비트 수입니다. 이 경우, 메시지는 2비트로 구성되므로 k = 2입니다.
• n은 코드워드(Codeword)의 비트 수입니다. 이 경우, 코드워드는 4비트로 구성됩니다. 따라서, n = 4입니다.
• r은 검사 비트(Redundancy)의 수입니다. 이 경우, r = n - k로 계산됩니다. 즉, r = 2입니다.
• 만약 "01101100"을 전송하려면, 이진수로 변환한 후에 블록 부호화를 적용해야 합니다. 이 경우, "01 10 11 00"은 메시지를 2비트씩 블록화하여 "0110 1100"으로 표현됩니다. 이 메시지를 위의 표에 따라 부호화하면, "01101100"은 부호화된 코드워드 "11110111"로 전송됩니다.

No error

만약 송신자가 "01"을 전송하려고 하고, 블록 부호화(Block Coding)를 적용하여 "011"을 전송했다고 가정하겠습니다. 수신자는 "011"을 정상적으로 수신했다면 다음과 같은 작업을 수행해야 합니다.

1. 검사 비트(Parity Bit) 검증

수신자는 받은 메시지에서 검사 비트를 분리하여 데이터워드(Dataword)를 추출합니다. 이 경우, 데이터워드는 "01"이 됩니다. 그런 다음, 수신자는 검사 비트를 다시 계산하여 계산된 검사 비트와 받은 메시지의 검사 비트가 일치하는지 확인합니다. 검사 비트가 일치한다면, 수신자는 오류가 발생하지 않았다는 것을 알 수 있습니다.

1. 데이터 추출

만약 검사 비트 검증이 성공했다면, 수신자는 데이터워드를 추출하여 원래의 메시지를 복원할 수 있습니다. 이 경우, 데이터워드는 "01"이므로, 수신자는 "01"이라는 메시지를 받았다는 것을 알 수 있습니다.

따라서, 수신자는 검사 비트 검증을 통해 오류가 없음을 확인하고, 데이터워드를 추출하여 메시지를 복원할 수 있습니다.

1-bit Error

만약 송신자가 "01"을 전송하려고 하고, 블록 부호화(Block Coding)를 적용하여 "011"을 전송했다고 가정하겠습니다. 수신자는 "111"이라는 메시지를 받았으며, 1비트 오류가 발생한 상황입니다.

수신자는 다음과 같은 절차를 통해 오류를 검출하고, 오류를 바로 잡을 수 있습니다.

1. 검사 비트(Parity Bit) 검증

수신자는 받은 메시지에서 검사 비트를 분리하여 데이터워드(Dataword)를 추출합니다. 이 경우, 데이터워드는 "01"이 됩니다. 그런 다음, 수신자는 검사 비트를 다시 계산하여 계산된 검사 비트와 받은 메시지의 검사 비트가 일치하는지 확인합니다. 검사 비트가 일치하지 않는다면, 수신자는 오류가 발생했음을 감지할 수 있습니다.

1. 오류 위치 식별

검사 비트 검증에서 오류가 발생했다면, 수신자는 어떤 비트에서 오류가 발생했는지 식별할 수 있어야 합니다. 이를 위해서는, 수신자는 받은 메시지와 계산된 검사 비트를 XOR 연산하여 오류 비트의 위치를 찾아낼 수 있습니다. 이 경우, "011"의 검사 비트는 "1"이므로, 수신자는 "111"과 "011"의 XOR 연산 결과인 "100"을 얻을 수 있습니다. 이 결과에서, 2진수로 변환한 값이 2자리이므로, 이진수에서 오류가 발생한 위치는 "100"의 마지막 1인 비트(가장 오른쪽 비트)입니다.

1. 오류 수정

수신자는 오류 위치를 찾았으므로, 해당 위치에 있는 비트를 반전시켜 오류를 수정할 수 있습니다. 이 경우, "111"에서 오류가 발생한 위치는 가장 오른쪽 비트이므로, 해당 비트를 반전시켜 "011"을 얻을 수 있습니다. 따라서, 수신자는 오류를 수정하고, 원래의 메시지 "01"을 복원할 수 있습니다.

결론적으로, 수신자는 검사 비트 검증을 통해 오류를 감지하고, XOR 연산을 통해 오류 위치를 식별하고, 오류를 수정하여 원래의 메시지를 복원할 수 있습니다.

2-bit error → 검출 못함

보내는 측은 "01"을 보내기 위해 "011"을 블록 코드로 인코딩하여 전송합니다. 그러나 수신 측이 "000"을 수신했습니다. 이 경우, 수신 측은 유효한 코드워드가 아닌 수신된 코드워드를 감지할 수 있습니다. 즉, 두 개 이상의 비트 오류가 발생했다는 것입니다.

오류를 감지하려면 수신 측은 오류 감지 기술을 사용할 수 있습니다. 수신된 코드워드를 코드북에 있는 유효한 코드워드와 비교하여 수신된 코드워드가 잘못되었음을 판단할 수 있습니다.

그러나 오류의 수가 감지할 수 있는 범위를 초과하였기 때문에, 수신 측은 오류를 수정할 수 없습니다. 수신 측은 보내는 측에게 다시 전송을 요청하거나, 다중 비트 오류를 수정할 수 있는 해밍 코드나 리드-솔로몬 코드와 같은 고급 오류 정정 기술을 사용하여 오류를 수정할 수 있습니다.

1-bit error → 오류 감지 + 오류 수정

예, 수신 측은 오류를 감지하는 것 외에도 오류 정정 기술을 사용하여 오류를 수정할 수 있습니다.

오류 정정 기술을 사용하여, 수신 측은 수신된 코드워드를 코드북에 있는 유효한 코드워드와 가장 가까운 코드워드로 수정할 수 있습니다. 이를 위해, 수신 측은 코드워드 간의 해밍 거리를 계산하여 오류를 수정합니다.

예를 들어, 수신 측이 "01001"을 수신하였고, 이것이 "01011"을 보내는 측이 보낸 유효한 코드워드에서 한 비트 오류가 있음을 감지했다고 가정합니다. 수신 측은 이 오류를 수정하기 위해 "01011"과 "01001" 간의 해밍 거리를 계산합니다. 이 경우, 해밍 거리는 1입니다. 그래서 수신 측은 오류가 있는 위치를 식별하고, 오류가 있는 비트를 뒤집어서 (0을 1로 또는 1을 0으로) 유효한 코드워드 "01011"으로 수정할 수 있습니다.

따라서, 오류 정정 기술을 사용하여 수신 측은 수신된 코드워드에서 비트 오류를 수정할 수 있으므로, 데이터 전송 중에 발생하는 오류를 처리할 수 있습니다.

송신자가 코드워드 "01011"을 보냅니다.
• 수신자는 "01001"을 수신합니다 (1비트 오류).
• 코드워드 중에서 01001에 가장 가까운 코드워드는 01011입니다.
• 따라서, 수신자는 데이터워드가 01이었을 것으로 추측합니다.

송신자가 코드워드 "01011"을 보냅니다.
• 수신자는 "01001"을 수신합니다 (1비트 오류).
• 2비트 이상의 오류는 없다고 가정하면, 이 코드워드 세트는 오류를 교정할 수 있습니다.

송신자가 코드워드 "01011"을 보냅니다.
• 수신자는 "00001"을 수신합니다 (2비트 오류).
• 이 경우, 가장 가까운 코드워드는 "00000"입니다 (잘못됨) - 이 코드워드는 2비트 오류를 교정할 수 없습니다.
• 그러나, 수신자는 오류가 있다는 것을 알고 있습니다. - "00001"이라는 코드워드가 없기 때문입니다. - 이 코드워드 세트는 2비트 오류를 검출할 수 있습니다. - 3비트 오류는 어떨까요? 이 코드워드 세트는 3비트 오류를 검출할 수 있지만, 교정은 불가능합니다. 3비트 오류가 발생하면, 2비트 이상의 오류가 발생했다는 것을 감지할 수 있습니다.

→ 1 bit error 검출 O, 교정O

→ 2 bit error 검출 O, 교정X

s-bit 오류를 감지하려면, 코드워드 집합의 MHD(Minimum Hamming Distance)는 s보다 커야합니다.

💡 dmin > s

코드워드의 MHD가 s+1인 경우를 가정해 보겠습니다.
어떤 코드워드를 선택하고 s 비트 이하를 변경합니다.
이 코드워드가 코드워드 집합에 없어야합니다. 그렇지 않으면 MHD는 s+1보다 작아져야 하기 때문입니다.

→ MHD가 2 이면 1 bit error를 검출할 수 있음!

t비트 오류를 수정하기 위해서는 코드워드 집합의 최소 해밍 거리(dmin)가 2t보다 커야 합니다.

💡 dmin > 2t

코드워드의 최소 해밍 거리(MHD)가 2t+1이라고 가정해 봅시다.
어떤 코드워드(C)를 선택한 후, t개의 비트를 변경하여 새로운 코드워드(C')를 만듭니다.
C'는 코드워드 집합에 속하지 않습니다.
그리고 C'와 가장 가까운 코드워드를 선택합니다.
해밍 거리가 t+1 이상인 다른 코드워드들을 제외하면, C이기 때문에 C가 선택됩니다.

→ MHD가 5 이면 2 bit error를 검출할 수 있음!

💡 detect(s) : dmin > s corret(t) : dmin > 2t

Q)

Suppose a codeword set has MHD=4.
• How many bit errors can this codeword set detect?

• How many bit errors can this codeword set correct?

만약 어떤 코드워드 집합의 최소 해밍 거리(MHD)가 4라면, 그 집합 안에 있는 두 코드워드 사이의 해밍 거리는 최소 4 이상입니다.

비트 에러를 감지하기 위해서는, 코드워드 집합의 MHD는 비트 에러의 수보다 커야 합니다. 따라서 이 코드워드 집합은 최대 3비트 에러를 감지할 수 있습니다. 4개 이상의 비트 에러가 있으면, 수신된 코드워드는 원래의 코드워드와는 다른 코드워드에 더 가까워질 것이므로, 수신자는 에러가 발생했다고 가정할 것입니다.

→ dmin>s

비트 에러를 수정하기 위해서는, 코드워드 집합의 MHD는 비트 에러의 두 배보다 커야 합니다. 따라서 이 코드워드 집합은 최대 1비트 에러를 수정할 수 있습니다. 2개 이상의 비트 에러가 있으면, 수신된 코드워드는 원래의 코드워드와는 다른 코드워드에 더 가까워질 것이므로, 수신자는 에러를 수정할 수 없을 것입니다.

→ dmin>2t

Linear block codes

설정된 코드워드 집합에서 두 코드워드를 선택합니다.
그리고 이 두 코드워드를 XOR 연산합니다.
이 결과로 나온 코드워드가 설정된 코드워드 집합에 속하면,
이 코드워드 집합은 선형 블록 코드라고 부릅니다.

모든 0으로 이루어진 코드워드를 제외하고 나머지 코드워드들의 1의 개수를 센다. 이 중에서 가장 작은 1의 개수가 해당 코드워드 집합의 최소 해밍 거리(MHD)이다.

Parity Bit

k 비트 데이터 워드 -> (k+1) 비트 코드 워드

• 1 비트 (패리티 비트) 추가
• 패리티 비트는 코드 워드에 1의 개수가 짝수가 되도록해야합니다.

💡 simple parity check codes

n = k+1
dmin = 2

Simple parity check code는 데이터 워드에 1개의 패리티 비트를 추가하여 오류를 감지하는 선형 블록 코드의 한 예시입니다. 데이터 워드를 이진 코드로 나타내고, 해당 코드의 모든 비트를 합하여 1의 개수가 홀수인지 짝수인지에 따라 패리티 비트를 정합니다. 이렇게 생성된 패리티 비트와 원래의 데이터 워드를 합쳐 (k+1)-비트 코드 워드를 생성합니다. 이 코드 워드는 전송 중에 손상될 수 있으며, 수신자는 코드 워드의 모든 비트를 합하여 1의 개수가 짝수인지 확인합니다. 만약 1의 개수가 홀수라면, 오류가 발생한 것으로 판단하고, 수신자는 해당 데이터 워드를 다시 요청합니다.

송신자가 패리티 검사 코드를 사용하여 데이터워드 '1011'을 전송합니다. - 코드워드는 '10111'입니다.

• 수신자가 '10111'을 수신하면, 수신자는 패리티 비트를 확인하여 데이터워드가 전송되었음을 감지합니다. 이 경우에는 전송이 정상적으로 완료되었으므로 수신자는 '10111'을 처리하고 해당 데이터를 사용합니다.

→ Error X

• 수신자가 '10011'을 수신하면, 데이터워드에 오류가 발생했음을 나타내는 홀수 개의 비트가 있는 것을 확인합니다. 이 경우, 오류를 검출하기 위해 수신자는 송신자에게 해당 데이터를 재전송하도록 요청해야 합니다.

→ 1-bit Error O

• 수신자가 '10110'을 수신하면, 수신자는 패리티 비트를 확인하여 데이터워드에 오류가 발생했음을 나타내는 홀수 개의 비트가 있는 것을 감지합니다. 이 경우, 수신자는 오류를 검출하고 송신자에게 해당 데이터를 재전송하도록 요청해야 합니다.

→ 1-bit Error O, 홀수갠데 parity bit이 0

Sender가 '10111'을 보낸 경우,

• Receiver가 '00110'을 받았을 때:
  • parity check에서 1의 개수가 홀수인 '1011'에 해당하는 dataword를 찾을 수 없으므로, 에러가 발생했다고 간주하고 재전송을 요청한다.
• Receiver가 '01011'을 받았을 때:
  • parity check에서 1의 개수가 홀수인 '1011'에 해당하는 dataword를 찾을 수 있으므로, 에러가 발생하지 않았다고 간주하고 데이터를 처리한다.

패리티 체크 코드는 1비트 에러는 감지할 수 있습니다. 만약 수신된 코드워드의 1 비트 수가 홀수(또는 짝수)이면, 전송된 코드워드에 오류가 있다는 것을 알 수 있기 때문입니다.

하지만 패리티 체크 코드는 2비트 오류를 감지할 수 없습니다. 전송된 코드워드에서 두 비트가 반전되면, 패리티 체크 코드는 오류를 감지하지 못합니다. 이 경우, 수신된 코드워드의 1의 개수는 여전히 짝수(또는 홀수)이고, 수신된 코드워드는 유효한 코드워드입니다.

패리티 체크 코드는 3비트 오류도 감지할 수 있습니다. 전송된 코드워드에서 3 비트 이상이 반전되면, 수신된 코드워드의 1의 개수는 다른 유효한 코드워드와 같아질 것입니다. 이 경우, 패리티 체크 코드는 오류를 감지하지 못하며, 어떤 데이터워드가 전송되었는지 구별할 수 없습니다.

패리티 체크 코드는 4비트 오류나 그 이상도 마찬가지입니다. 수신된 코드워드는 다른 데이터워드를 가진 유효한 코드워드일 뿐이며, 패리티 체크 코드는 오류를 감지할 수 없습니다.

💡 → Parity check는 홀수개의 오류만 검출할 수 있다

1. 패리티 검사(Parity Check)

1의 개수를 짝수 개로 맞춰서 보낼지(Even Parity), 홀수 개로 맞춰서 보낼지(Odd Parity) 송신측과 수신측이 약속하고 여분의 bit(패리티 비트)를 채워 보내는 것입니다.

하지만 패리티 비트는 Single-bit Error와 같이 홀수 개의 오류만 검출할 수 있고, 짝수 개의 오류는 검출하지 못하는 문제점이 발생합니다.

→ 이를 해결하기 위해 Two-dimensional Parity Check(2차원 패리티 검사)가 나왔습니다.

Two-dimensional Parity Check는 수평(LRC: Longitudinal Redundancy Check)과 수직(VRC: Vertical Redundancy Check)으로 패리티 비트를 추가하고, 모두 카운트합니다. 만약 수평에서 짝수 개의 비트가 바뀐다고 해도 수직 패리티 검사에서 검출할 수 있습니다.

하지만 수평과 수직으로 짝수 개씩 똑같이 바뀐다면 검출이 불가능 합니다. 근본적으로 이러한 패리티 비트의 한계가 있기 때문에 에러 검출 능력이 떨어집니다.

ex) Even Parity에서 검출 불가

sent                 received

1001 l 0            1001 l 0

0110 l 0            0000 l 0

0110 l 0    ->     0000 l 0

1001 l 0            1001 l 0

ㅡㅡㅡ 0             ㅡㅡㅡ 0

0000   0            0000  0

Two-dimensional Parity Check는 2차원 행렬의 형태로 데이터를 전송하는 오류 검출 방식입니다. 이 방식은 데이터를 일정한 크기의 블록으로 분할하고, 각 블록의 행과 열을 기준으로 각각 패리티 비트를 계산하여 전송합니다.

이렇게 전송된 데이터가 수신측에서 받아질 때, 각 블록의 행과 열의 패리티 비트를 검사하여 오류 여부를 판단합니다. 만약 특정 블록의 패리티 비트가 일치하지 않는다면, 해당 블록이 손상되었다는 것을 의미하며, 오류 검출이 가능합니다.

Two-dimensional Parity Check는 단순한 오류 검출 방식으로서, 단일 비트 오류 뿐만 아니라 다중 비트 오류도 검출할 수 있습니다. 그러나 오류 정정까지는 처리할 수 없으므로, 오류 검출 기능만을 가지고 있습니다.\

2차원 패리티 검사는 1비트 오류를 검출하고 위치를 파악할 수 있지만, 수정은 할 수 없습니다. 만약 패리티 비트 중 하나에 오류가 있으면 이를 검출할 수 있지만, 어떤 데이터 비트에서 오류가 발생했는지를 알 수는 없습니다. 이 방식은 오류가 한 행 또는 열에 있는지 여부만을 알려줄 뿐입니다. 오류가 검출되면 수신자는 송신자에게 데이터 블록을 재전송하도록 요청하여 오류가 없는 전송을 보장합니다.

Hamming(7,4) 코드는 4-bit 데이터워드를 7-bit 코드워드로 바꾸는 선형 블록 코드이다. 이 코드는 데이터 워드에 3개의 패리티 비트를 추가하여 전송 중 발생하는 오류를 검출 및 수정할 수 있다.

각각의 데이터 워드는 4개의 비트로 구성되며, 이 코드는 4비트 데이터 워드를 7비트 코드 워드로 변환한다. 변환 방법은 다음과 같다.

• 4개의 데이터 비트를 입력으로 사용한다.
• 3개의 패리티 비트를 추가한다.
• 각각의 패리티 비트는 입력 데이터 비트 중 일부를 사용하여 계산된다. 각 패리티 비트는 각기 다른 비트 위치에서 계산되며, 오류를 검출하기 위한 검사 비트로 사용된다.

이 코드는 단일 비트 오류를 검출하고 수정할 수 있다. 코드 워드 내에서 단일 비트 오류가 발생하면, 해당 비트 위치를 특정하여 수정할 수 있다. 하지만, 2개 이상의 비트 오류가 발생하면 이 코드는 해당 오류를 검출할 수 있지만 수정할 수 없다.

→ 1-bit error : 검출O, 수정O

→ 2-bit error이상 : 검출O, 수정X

해밍(7,4) 코드에서 체크 비트는 데이터 비트와 함께 전송되는 추가 비트입니다. 이 코드에서는 총 3개의 체크 비트가 사용됩니다. 각 체크 비트는 특정 데이터 비트 그룹에 대한 패리티를 나타내며, 이를 통해 오류를 감지합니다.

j번째 비트를 검사하는 경우, j와 AND 연산을 수행하여 k번째 비트를 선택합니다. 예를 들어, 1번째 비트는 3번째, 5번째 및 7번째 비트의 값을 XOR합니다. 따라서 001 & 011 = 001, 001 & 101 = 001, 001 & 111 = 001이 됩니다.

→ 1,3,5,7 의 1의 합이 짝수가 되도록 1을 고름

→ 2,3,6,7 의 1의 합이 짝수가 되도록 1을 고름

→ 4,5,6,7 의 1의 합이 짝수가 되도록 1을 고름

Hamming (7,4) 코드는 최소 해밍 거리 (MHD)가 3입니다.

해밍 거리를 계산하려면 가능한 모든 코드워드 쌍을 고려하여 해밍 거리를 계산해야 합니다. 이 코드는 16개의 가능한 코드워드 (2^4)가 있으므로 16개 중 2개를 선택하여 총 16 choose 2 (즉, 16! / ((16-2)!2!) = 120)개의 코드워드 쌍을 비교해야 합니다.

그러나 우리는 서로 다른 두 코드워드는 적어도 3개의 위치에서 다른 것으로 나타난다는 것을 알 수 있습니다. 이것은 각 코드워드가 3개의 검사 비트를 갖고 있으며, 이러한 검사 비트는 서로 다른 두 코드워드가 동일한 검사 비트 집합을 가지지 않도록 선택된 것입니다. 따라서 Hamming (7,4) 코드의 MHD는 3입니다.

n 비트 코드워드에서 1 비트 오류를 수정하기 위해서는, 수신기가 다음 중 하나를 올바르게 선택할 수 있어야 합니다:

• 오류 없음
• 첫 번째 비트에 오류가 있는 경우
• 두 번째 비트에 오류가 있는 경우
• 세 번째 비트에 오류가 있는 경우
• ...
• (n-1)번째 비트에 오류가 있는 경우
• n 번째 비트에 오류가 있는 경우

이렇게 되면 총 n+1개의 경우가 있습니다.

n비트 코드워드에서 1비트 에러를 수정하기 위해서는 n+1개의 정보가 필요합니다.
따라서 n+1개의 정보를 넣기 위해서는 log2(n+1)비트가 필요합니다.
따라서 해밍 코드는 1비트 에러를 수정하기 위한 최소 비용을 사용합니다.
해밍 코드는 완벽한 코드로서, 더 나은 방법이 없습니다.

그래서 hamming(7,4)code를 사용하는것!

Voting

Hamming 거리를 증가시키는 가장 간단한 방법은 '0'을 N 개의 '0'으로 변환하는 것입니다. 예를 들어, n = 3이면 '0'은 '000'으로, '1'은 '111'로 변환됩니다. 이렇게 하면 Hamming 거리가 N이 됩니다. 만약 수신자가 '010'을 수신하면, 코드워드에 0이 1보다 많으므로 0으로 해석됩니다. 이러한 방식을 투표(voting) 방식이라고 합니다.

7비트 코드워드에서 1비트 오류를 수정하려면 3개의 제어 비트(컨트롤 비트) - 8개의 정보 조각이 필요합니다.
일반적으로 (2^k-1)비트 코드워드가 있으면, 1비트 오류를 수정하기 위해서는 k개의 제어 비트가 필요합니다.
k=4인 경우, Hamming(15,11) 코드를 얻습니다.
k=5인 경우, Hamming(31,26) 코드를 얻습니다.
k가 증가함에 따라 효율성이 증가합니다.

즉,

제어 비트의 크기 = k
• 코드워드의 크기 = 2k -1
• 데이터워드의 크기 = 2k -1-k
• 효율성 = (2k -1-k) / (2k -1)
• k가 증가함에 따라 효율성이 증가합니다.
• 그러나 데이터워드가 길어질수록 2개 이상의 비트 에러가 발생할 가능성이 높아져 에러 검출 비율이 감소합니다.

4비트를 사용하여 숫자 -6을 나타내야 하는 상황이라고 가정해봅시다.
• -6을 1의 보수를 이용하여 나타냅니다.
• 1의 보수를 구하는 방법은 모든 비트를 반전시키는 것입니다.
• 따라서 6을 2진수로 나타내면 0110이 됩니다.
• 6의 1의 보수는 1001이 됩니다.
• 따라서 -6은 1001로 표현됩니다.
• 이진수 1001을 10진수로 변환하면 9가 됩니다.

Q)

Suppose the divisor has x0
term, and has at least one
other term
– e.g. g(x) = x2+1
• Then, all 1-bit errors can be detected
• Why?

CRC가 어떤 경우에 오류를 감지하지 못할까요?

• 오류가 발생했지만 수정된 코드워드 T'(x)가 g(x)로 나누어 떨어지는 경우
  → 오류 감지 실패
• T'(x) = T(x) + e(x) - 여기서 e(x)는 오류를 나타냄 - 만약 T(x) + e(x)가 g(x)로 나누어 떨어진다면, 수신자는 코드워드가 올바르게 수신된 것으로 인식합니다.
• CRC의 오류 감지 성능은 g(x)에 따라 달라집니다.

만약 나누는 다항식 g(x)가 x0 항과 적어도 하나의 다른 항을 가지고 있다면, 그 다항식은 최소 1의 차수를 갖게 됩니다. 이는 전송된 코드워드에 1비트 에러가 발생하면 수신된 코드워드도 적어도 한 비트는 다르게 되도록 만듭니다. 만약 x0 위치에서 오류가 발생하면 결과적으로 코드워드에는 x0 항이 존재하게 되는데, 이는 x 항을 갖지 않는 g(x) = x2 + 1로 나누어 떨어지지 않습니다. 만약 다른 위치에서 오류가 발생하면, 결과적으로 코드워드에는 0이 아닌 x 항이 존재하게 되고 마찬가지로 g(x)로 나누어 떨어지지 않습니다. 따라서 두 경우 모두에 대해, CRC로 오류가 검출됩니다.

💡 detect(s) : dmin > s corret(t) : dmin > 2t 💡 simple parity check codes

n = k+1
dmin = 2

💡 Hamming code

dmin = 3

💡 Size of the control bits = k Size of the codeword = 2^k-1 Size of the dataword = 2^k-1-k Efficiency rate = (2^k-1-k) / (2^k-1)