해밍 코드

바이너리 해밍 코드
바이너리 해밍 코드
	해밍(7,4) 코드(r = 3)
이름을 따서 명명됨	리처드 해밍
분류
유형	선형블록코드
블록 길이	2r - 1 여기서 r ≥ 2
메시지 길이	2r − r − 1
등급	1 − r/(2r − 1)
거리	3
알파벳 크기	2
표기법	[2r - 1, 2r - r - 1, 3]-2코드
특성.
	완벽한 암호
	v; t;

컴퓨터 과학과 통신에서 해밍 코드는 선형 오류 수정 코드의 계열이다. 해밍 코드는 수정되지 않은 오류를 감지하지 않고 1비트 및 2비트 오류를 감지하거나 1비트 오류를 수정할 수 있다. 대조적으로 단순 패리티 코드는 오류를 수정할 수 없고, 오류의 홀수 비트만 감지할 수 있다. 해밍 코드는 완벽한 코드, 즉 블록 길이와 최소 거리 3개로 코드에 대해 가능한 최고 속도를 달성한다.^[1] 리처드 W. 해밍은 펀치된 카드 판독기에 의해 도입된 오류를 자동으로 수정하는 방법으로 1950년에 해밍 코드를 발명했다. 해밍은 당초 논문에서 자신의 일반적인 생각을 상세히 설명했지만, 구체적으로 4비트의 데이터에 3개의 패리티 비트를 추가하는 해밍(7,4) 코드에 초점을 맞췄다.^[2]

수학적 용어로 해밍 코드는 이진 선형 코드의 한 종류다. 각 정수 $r$ ≥ $2$ 에 대해 블록 길이가 $n$ = 2 - $1$ 이고^r 메시지 $길이$ k = $2 r$ - r - $1인$ 코드가 있다. 따라서 해밍 코드의 비율은 $R$ = k / $n$ = $1$ - $r$ / $(2 r$ - 1)이며 $,$ 이는 최소 거리가 3인 코드(즉, 코드 워드에서 다른 코드 워드로 이동하는 데 필요한 최소 비트 수)와 $블록 r$ 길이 2 - $1인$ 코드에서 가장 높은 것이다. 해밍 코드의 패리티-체크 매트릭스는 0이 아닌 길이 r의 $모든$ 열을 나열하여 구성되는데, 해밍 코드의 이중 코드는 단축된 하다마드 코드임을 의미한다. 패리티-체크 매트릭스에는 두 개의 열이 쌍으로 선형적으로 독립되어 있다는 속성이 있다.

해밍 코드가 데이터에 추가하는 제한된 중복성 때문에 오류율이 낮을 때만 오류를 감지하고 수정할 수 있다. 비트 오류가 극히 드물고 해밍 코드가 널리 사용되는 컴퓨터 메모리(일반적으로 RAM)의 경우가 그러하며, 이 보정 시스템을 갖춘 RAM은 ECC RAM(ECC 메모리)이다. 이러한 맥락에서, 하나의 추가 패리티 비트가 있는 확장 해밍 코드가 종종 사용된다. 확장 해밍 코드는 해밍 거리 4를 달성하여 디코더가 최대 1비트 오류가 발생할 때와 2비트 오류가 발생할 때를 구별할 수 있다. 이러한 의미에서 확장 해밍 코드는 SECED라고 약칭되는 단일 오류 수정 및 이중 오류 검출이다.

역사

해밍 코드의 발명가 리처드 해밍은 1940년대 후반 벨 연구소에서 사이클 타임(초 단위)을 갖는 전자기계 계전기 기반 기계인 벨 모델 V 컴퓨터에서 일했다. 입력은 한 줄에 최대 6개의 구멍이 뚫린 7/8인치 폭의 펀치된 종이 테이프에 주입되었다. 평일에는 계전기 오류가 감지되면 기계가 정지하고 플래시를 점등해 작업자가 문제를 해결할 수 있도록 했다. 근무시간 이후와 주말, 운영자가 없을 때 기계는 단순히 다음 작업으로 넘어갔다.

해밍은 주말에 일을 했고, 감지된 오류로 인해 프로그램을 처음부터 다시 시작해야 하는 것에 대해 점점 더 좌절감을 느꼈다. 해밍은 녹음된 인터뷰에서 "이런 젠장, 기계가 오류를 감지할 수 있다면 왜 오류의 위치를 찾아 수정하지 못하는 거지?"^[3]라고 말했다. 이후 몇 년 동안 그는 오류 수정 문제를 연구하면서 점점 더 강력한 알고리즘을 개발했다. 1950년에 그는 현재 ECC 메모리와 같은 어플리케이션에서 사용되고 있는 해밍 코드라고 알려진 것을 발표하였다.

해밍 이전의 코드

해밍 코드 이전에는 수많은 간단한 오류 감지 코드가 사용되었지만, 같은 공간 오버헤드에서는 해밍 코드만큼 효과적인 코드가 없었다.

패리티

패리티는 앞의 데이터의 비트 수(값이 1인 비트 위치)가 짝수인지 홀수인지를 나타내는 단일 비트를 추가한다. 전송에서 비트의 홀수가 변경되면 메시지가 패리티를 변경하고 이 시점에서 오류를 감지할 수 있지만 변경된 비트는 패리티 비트 자체였을 수 있다. 가장 일반적인 관례는 패리티 값이 1이면 데이터에 홀수 수가 있고 패리티 값이 0이면 짝수 수가 있다는 것이다. 변경된 비트 수가 짝수일 경우 체크 비트가 유효하고 오류가 감지되지 않는다.

더욱이 패리티는 어떤 비트가 오류를 감지할 수 있는 경우에도 오류를 포함하는지를 나타내지 않는다. 데이터는 완전히 폐기하고 처음부터 다시 전송해야 한다. 시끄러운 전송 매체에서 성공적인 전송은 오랜 시간이 걸리거나 결코 일어나지 않을 수 있다. 다만 패리티 점검의 품질은 열악하지만, 단 비트만 사용하기 때문에 이 방법은 오버헤드를 최소화할 수 있다.

5개 코드 중 2개

5개 중 2개 코드는 정확히 3개의 0과 2개의 1로 구성된 5개의 비트를 사용하는 인코딩 방식이다. 이것은 숫자 0~9를 나타내기에 충분한 10개의 가능한 조합을 제공한다. 이 계획은 모든 단일 비트 오류, 모든 홀수 비트 오류 및 일부 짝수 비트 오류(예: 양쪽 1비트의 플립)를 감지할 수 있다. 그러나 그것은 여전히 이러한 오류들을 시정할 수 없다.

반복

당시 사용 중인 또 다른 코드는 데이터 비트가 올바르게 전송되었는지 확인하기 위해 모든 데이터 비트를 여러 번 반복했다. 예를 들어 보낼 데이터 비트가 1이면 n = 3 반복 코드가 111을 전송한다. 수신된 3비트가 동일하지 않으면 전송 중에 오류가 발생했다. 채널이 충분히 깨끗하면 3중마다 1비트만 바뀌는 경우가 대부분이다. 따라서 001, 010, 100은 각각 0비트에 해당하는 반면 110, 101, 011은 1비트에 해당하며, 더 많은 자릿수는 데이터 비트가 되어야 하는 것을 나타낸다. 오류가 있는 상태에서 원본 메시지를 재구성할 수 있는 이 기능을 가진 코드를 오류 수정 코드라고 한다. 이 삼중 반복 코드는 2개의 패리티 비트가 있고 2 - 2 - 1 = 1 데이터² 비트가 있기 때문에 m = 2를 갖는 해밍 코드다.

그러나 이러한 코드가 모든 오류를 올바르게 복구할 수는 없다. 본 예에서 채널이 2비트를 넘기고 수신기가 001을 얻으면 시스템은 오류를 감지하지만, 원래 비트가 0이라고 결론을 내리는데, 이는 잘못된 것이다. 비트 문자열 크기를 4개로 늘리면 2비트 오류를 모두 감지할 수 있지만 수정할 수는 없다(패리티 비트의 양은 짝수임). 5비트에서는 3비트 오류를 모두 감지하고 수정할 수 있지만 3비트 오류는 모두 수정할 수 없다.

더구나 패리티 비트 문자열의 크기를 늘리는 것은 비효율적이어서 원래 사례에서 처리량을 3배 정도 줄였고, 더 많은 오류를 감지하고 수정하기 위해 각 비트가 중복되는 횟수를 늘리면 효율성이 급격히 떨어진다.

설명

메시지에 오류 수정 비트가 더 많이 포함되고, 잘못된 비트가 서로 다른 오류 결과를 생성하도록 해당 비트가 배열될 수 있다면, 불량 비트를 식별할 수 있다. 7비트 메시지에는 7개의 단일 비트 오류가 있을 수 있으므로 3개의 오류 제어 비트는 오류가 발생했다는 것뿐만 아니라 오류를 발생시킨 비트도 잠재적으로 지정할 수 있다.

해밍은 5분의 2를 포함한 기존의 코딩 방식을 연구했고, 그 개념을 일반화했다. 우선, 그는 블록의 데이터 비트 수와 오류 수정 비트의 수를 포함하여 시스템을 설명하는 명명법을 개발했다. 예를 들어 패리티는 모든 데이터 워드에 대해 하나의 비트를 포함하므로, 7비트의 ASCII 단어를 가정하면, 해밍은 이것을 (8,7) 코드로 설명했으며, 그 중 7비트가 데이터라고 한다. 반복 예는 같은 논리를 따르는 (3,1)일 것이다. 코드율은 두 번째 숫자를 첫 번째 숫자로 나눈 값입니다, 반복 예시, 1/3입니다.

해밍은 또한 두 개 이상의 비트를 플립하는 것의 문제를 알아차렸고, 이것을 "거리"(지금은 해밍 거리, 그의 이름을 따서 해밍 거리라고 부른다)라고 묘사했다. 패리티의 거리는 2이므로, 1비트 플립은 감지할 수 있지만 보정할 수 없으며, 어떤 2비트 플립도 보이지 않게 된다. (3,1) 반복은 3의 거리를 가지는데, 3비트를 같은 3중으로 뒤집어야 눈에 보이는 오류가 없는 또 다른 코드 단어를 얻을 수 있기 때문이다. 1비트 오류를 수정하거나 2비트 오류를 탐지할 수 있지만 정확하지는 않다. A (4,1) 반복 (각 비트는 4회 반복)의 거리는 4이므로 3비트를 뒤집는 것은 감지할 수 있으나 수정되지는 않는다. 같은 그룹에서 3비트가 뒤집힐 때 수정을 시도하면 잘못된 코드 단어가 생성되는 상황이 발생할 수 있다. 일반적으로 거리 k가 있는 코드는 k - 1 오류를 검출할 수 있지만 교정할 수는 없다.

해밍은 가능한 한 거리를 늘리는 동시에 가능한 한 코드 속도를 높이는 두 가지 문제에 관심을 보였다. 1940년대 동안 그는 기존의 코드들을 획기적으로 개선한 몇 개의 인코딩 체계를 개발했다. 그의 모든 시스템의 핵심은 패리티 비트가 서로 겹치는 것이었고, 그래서 그들은 데이터뿐만 아니라 서로를 확인할 수 있었다.

일반 알고리즘

다음 일반 알고리즘은 비트 수에 관계없이 단일 오류 수정(SEC) 코드를 생성한다. 주요 아이디어는 인덱스-XOR(1을 포함하는 모든 비트 위치의 XOR)가 0이 되도록 오류 수정 비트를 선택하는 것이다. 오류 수정 비트로 1, 10, 100 등(이진수)을 사용하고 있는데, 이는 전체 메시지의 인덱스-XOR가 0이 되도록 오류 수정 비트를 설정할 수 있음을 보장한다. 수신기가 인덱스-XOR 0의 문자열을 수신하면 손상이 없었다고 결론을 내릴 수 있고, 그렇지 않으면 인덱스-XOR는 손상된 비트의 인덱스를 표시한다.

알고리즘은 다음 설명에서 추론할 수 있다.

1부터 시작하는 비트의 번호를 비트 1, 2, 3, 4, 5, 6, 7 등으로 매긴다.
비트 번호는 1, 10, 11, 100, 101, 110, 111, 111 등 2진수로 작성한다.
2의 힘을 가진 모든 비트 위치(1비트의 이진 형태에 1비트가 있음)는 패리티 비트 1, 2, 4, 8 등(1, 10, 100,
위치의 이진 형태로 2개 이상의 비트가 있는 다른 모든 비트 위치는 데이터 비트다.
각 데이터 비트는 비트 위치의 이진 형식으로 결정되는 2개 이상의 패리티 비트의 고유한 집합에 포함된다.
1. 패리티 비트 1은 비트 1(패리티 비트 자체), 3, 5, 7, 9 등 최하위 비트 세트가 있는 모든 비트 위치를 포괄한다.
2. 패리티 비트 2는 비트 2-3, 6-7, 10-11 등 두 번째로 중요도가 낮은 비트 세트를 모두 포함한다.
3. 패리티 비트 4는 세 번째로 중요도가 낮은 비트(비트 4–7, 12–15, 20–23 등)가 설정된 모든 비트 위치를 다룬다.
4. 패리티 비트 8은 네 번째로 중요도가 낮은 비트(비트 8–15, 24–31, 40–47 등)가 설정된 모든 비트 위치를 다룬다.
5. 일반적으로 각 패리티 비트는 패리티 위치의 비트 와이즈 AND와 비트 위치가 0이 아닌 모든 비트를 포함한다.

인코딩할 데이터의 바이트가 10011010이면 데이터 워드(_를 사용하여 패리티 비트를 나타냄)는 __1_001_1010이고, 코드 워드는 011100101010이다.

패리티의 선택은 짝수 또는 홀수와는 무관하지만 인코딩과 디코딩 모두에 동일한 선택을 사용해야 한다.

이 일반 규칙은 다음과 같이 시각적으로 보여질 수 있다.

인코딩된 데이터 비트		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
비트 위치		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
패리티 물다 보도	p1
	p2
	p4
	p8
	p16

표시된 것은 인코딩된 비트 20개(패리티 5개, 데이터 15개)에 불과하지만 패턴은 무한정 지속된다. 육안 검사에서 볼 수 있는 해밍 코드의 핵심은 주어진 비트가 고유한 패리티 비트 세트에 포함된다는 것이다. 오류를 확인하려면 모든 패리티 비트를 확인하십시오. 에러 증후군으로 불리는 에러 패턴은 에러 비트를 식별한다. 모든 패리티 비트가 올바르면 오류가 없다. 그렇지 않으면 잘못된 패리티 비트의 위치 합계가 잘못된 비트를 식별한다. 예를 들어 위치 1, 2, 8의 패리티 비트가 오류를 나타내면 비트 1+2+8=11이 오류인 것이다. 패리티 비트가 하나만 오류를 나타내면 패리티 비트 자체가 오류인 것이다.

$m$ 패리티 비트를 사용하면 1~ $2^{m}-1$ - $2^{m}-1$ {\ $디스플레이$ 스타일 $2^{m$ }-1 $}까지의$ 비트를 커버할 수 있다 $2^{m}-1$ . 패리티 비트를 할인한 후 $2^{m}-m-1$ - $2^{m}-m-1$ - $2^{m}-m-1$ $2^{m}-m-1$ 비트가 $2^{m}-m-1$ 남아 데이터로 사용할 수 있다. $m$ 이 다르기 때문에 가능한 모든 해밍 코드는

패리티 비트	총 비트 수	데이터 비트	이름	등급
2	3	1	해밍(3,1) (트리플 반복 코드)	1/3 ≈ 0.333
3	7	4	해밍(7,4)	4/7 ≈ 0.571
4	15	11	해밍(15,11)	11/15 ≈ 0.733
5	31	26	해밍(31,26)	26/31 ≈ 0.839
6	63	57	해밍(63,57)	57/63 ≈ 0.905
7	127	120	해밍(127,120)	120/127 ≈ 0.945
8	255	247	해밍(255,247)	247/255 ≈ 0.969
…
$m$	$n=2^{m}-1$	$k=2^{m}-m-1$	해밍 $(2^{m}-1,2^{m}-m-1)$ - $(2^{m}-1,2^{m}-m-1)$ , $(2^{m}-1,2^{m}-m-1)$ - m $(2^{m}-1,2^{m}-m-1)$ - $(2^{m}-1,2^{m}-m-1)$ ) ${\디스플레이$ 스타일(2 $^{m}-1$ ,2 $^{m}-m-1)}$	${\displaystyle(2^{m}-m-1)/(2^{m}-1)}$

추가 패리티가 있는 해밍 코드(SECED)

해밍 코드는 최소 거리 3이므로 디코더가 단일 오류를 감지하고 수정할 수 있지만 일부 코드 워드의 이중 비트 오류와 다른 코드 워드의 단일 비트 오류를 구분할 수 없다. 따라서 일부 이중 비트 오류는 단일 비트 오류인 것처럼 잘못 디코딩되므로 보정을 시도하지 않는 한 감지되지 않는다.

이러한 단점을 보완하기 위해 해밍 코드는 추가 패리티 비트로 확장할 수 있다. 이렇게 하면 해밍 코드의 최소 거리를 4로 늘릴 수 있어 디코더가 단일 비트 오류와 2비트 오류를 구별할 수 있다. 따라서 디코더는 단일 오류를 감지하고 수정할 수 있으며 동시에 이중 오류를 감지(수정하지는 않음)할 수 있다.

디코더가 오류를 수정하려 하지 않으면 트리플 비트 오류를 안정적으로 감지할 수 있다. 디코더가 오류를 수정하면 일부 삼중 오류는 단일 오류로 오인되고 잘못된 값으로 "수정"된다. 따라서 오류 보정은 확실성(트리플 비트 오류를 신뢰성 있게 감지하는 능력)과 복원력(단일 비트 오류에도 계속 기능하는 능력) 사이의 절충이다.

이 확장된 해밍 코드는 SECED(단일 오류 수정, 이중 오류 검출로 약칭)로 알려진 컴퓨터 메모리 시스템에서^{[citation needed]} 인기가 있다.^{[citation needed]} 특히 인기 있는 코드는 잘린(127,120) 해밍 코드에 추가 패리티 비트를^{[citation needed]} 더한 (9,8) 패리티 코드와 공간 오버헤드가 같다.

[7,4] 해밍코드

4개의 데이터 비트 및 3개의 패리티 비트와 어떤 패리티 비트가 어떤 데이터 비트에 적용되는지 그래픽으로 표시

1950년에 해밍은 [7,4] 해밍 코드를 도입하였다. 3개의 패리티 비트를 추가하여 4개의 데이터 비트를 7비트로 인코딩한다. 단일 비트 오류를 감지하고 수정할 수 있다. 전체 패리티 비트가 추가되면 이중 비트 오류도 감지할 수 있지만 정확하지는 않다.

G와 H의 건설

매트릭스 G $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}$ ( $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}$ I $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}$ - $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}$ $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}$ ) ${\$ $T}\\\end{array}\end{pmatrix}}}$ 은(는) 선형(n,k) 코드의 (수동) 제너레이터 행렬이라고 하며 $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}$ ,

및 $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{n-k}\\\end{array}}\end{pmatrix}}$ $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{n-k}\\\end{array}}\end{pmatrix}}$ ( A $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{n-k}\\\end{array}}\end{pmatrix}}$ $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{n-k}\\\end{array}}\end{pmatrix}}$ - $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{n-k}\\\end{array}}\end{pmatrix}}$ ) ${\$ $I_{n-k}\\end{array}\end{pmatrix}}}$ 을(를) 패리티 확인 매트릭스라고 한다 $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{n-k}\\\end{array}}\end{pmatrix}}$ .

이것은 표준(또는 체계적) 형태의 G와 H를 구성하는 것이다. 형태에 관계없이 선형 블록 코드의 G와 H는 충족되어야 한다.

${\$ $T}}=\mathbf{0}},$ 전체 0 행렬 $\mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0}$ ^[4]

[7, 4, 3] = [n, k, d] = [2^m - 1, 2-1-m^m, 3]이기 때문이다. 해밍 코드의 패리티-체크 매트릭스 H는 쌍으로 독립된 길이 m의 모든 열을 나열하여 구성된다.

따라서 H는 매트릭스 열의 n-tuple 순서가 중요하지 않은 모든 0이 아닌 n-tuple인 매트릭스다. 오른쪽은 (n - k)-identity 행렬일 뿐이다.

그래서 G는 G의 왼쪽에 있는 신분 k-identity 매트릭스와 함께 H의 좌측 전치부를 취함으로써 H로부터 얻을 수 있다.

코드 생성기 매트릭스 $\mathbf {G}$ ${\$ 및 $\mathbf {G}$ 패리티 검사 매트릭스 $\mathbf {H}$ ${\$ 는) 다음과 $\mathbf {H}$ 같다.

$\mathbf{G} :={\begin{pmatrix}1&0&1&1&0&1&0&0&1&0&1\\\0&0&0&0&1&1\\\nd{pmatrix}}}{pmatrix}}}}}}}}}{0&0&0&#0&#1&#1,7$

그리고

$\mathbf {H} :={\begin{pmatrix}1&0&1&1&1&1&1&0&0&0\\\1&1&1&1&0&#0&#1&#1&#1&1\end{pmatrix}}}.$

마지막으로, 다음과 같은 작업에 의해 이러한 행렬을 동등한 비시스템 코드로 변경할 수 있다.^[4]

열 순열(열 교환)
기본 행 작업(행의 선형 조합으로 행 교체)

인코딩

예

위의 매트릭스에서 우리는^k 2 = 2⁴ = 16개의 코드 단어를 가지고 있다. Let ${\vec {a}}$ be a row vector of binary data bits, ${\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}$ . 코드 ${\vec {x}}$ x ${\vec {x}}$ → ${\$ 가능한 16개 데이터 벡터 ${\vec {a}}$ 하나에 대한 ${\vec {x}}$ 코드 워드 x → ${\$ 은(는) 표준 매트릭스 ${\vec {x}}={\vec {a}}G$ x ${\vec {x}}={\vec {a}}G$ → a ${\vec {x}}={\vec {a}}G$ → ${\vec {x}}={\vec {a}}G$ = ${\vec {x}}={\vec {a}}G$ ${\vec {{x}={\vec {a}G}$ 에서 제공되며 ${\vec {a}}$ 여기서 ${\vec {x}}={\vec {a}}G$ 요약 작업이 수행된다.

${\vec {a}}=[1,0,1,1]$ 를 들어 ${\vec {a}}=[1,0,1,1]$ ${\vec {a}}=[1,0,1,1]$ → ${\vec {a}}=[1,0,1,1]$ = ${\vec {a}}=[1,0,1,1]$ [ 1, ${\vec {a}}=[1,0,1,1]$ ${\vec {a}}=[1,0,1,1]$ , 1 ${\vec {a}}=[1,0,1,1]$ ] ${\displaystyle {\vec{a}=[$ 1, $0,1,1,1]}$ 을(를) 두십시오 ${\vec {a}}=[1,0,1,1]$ 위의 $G$ 제너레이터 매트릭스 $G$ $G$ 을(모듈로 2를 적용한 후 합계에)

${\displaystyle{\vec{)}}={\vec{}}G={\begin{pmatrix}1&, 0&, 1&, 1\end{pmatrix}}{\begin{pmatrix}1&, 0&, 0&, 0&, 1&, 1&, 0\\0&, 1&, 0&, 0&, 1&, 0&, 1\\0&, 0&, 1&, 0&, 0&, 1&, 1\\0&, 0&, 0&, 1&, 1&, 1&, 1\\\end{pmatrix}}={\begin{pmatrix}1&, 0&, 1&, 1&, 2&, 3&, 2\end{pmatrix}}={\begin{pmatrix}1&, 0&, 1&, 1&, 0&, 1&, 0\end{pmatrix}}}$

[7,4] 패리티 비트가 추가된 해밍 코드

추가 패리티 비트를 사용한 위의 [7,4] 예. 이 다이어그램은 이 예에서 행렬 H에 해당하지 않는다.

[7,4] 해밍 코드는 (7,4) 인코딩 워드 위에 추가 패리티 비트를 추가함으로써 [8,4] 코드로 쉽게 확장할 수 있다(해밍(7,4 참조). 이는 수정된 행렬로 요약할 수 있다.

\mathbf {G} :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}

그리고

\mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}.

H는 표준형식이 아니라는 점에 유의한다. G를 얻기 위해 기초 행 연산을 사용하여 H와 동등한 행렬을 체계적 형태로 얻을 수 있다.

\mathbf {H} =\left({\begin{array}{cccc cccc}0&1&1&1&1&0&0&0\\1&0&1&1&0&1&0&0\\1&1&0&1&0&0&1&0\\1&1&1&0&0&0&0&1\end{array}}\right)_{4,8}.

예를 들어, 이 행렬의 첫 번째 행은 비체계적 형태의 H의 두 번째 행과 세 번째 행의 합이다. 위의 해밍 코드에 대한 체계적 구조를 이용하여 매트릭스 A가 뚜렷하고 G의 체계적 형태가 다음과 같이 기록된다.

\mathbf {G} =\left({\begin{array}{cccc cccc}1&0&0&0&0&1&1&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&0&1\\0&0&0&1&1&1&1&0\end{array}}\right)_{4,8}.

비시스템적 형태의 G는 이 행렬과 일치하도록 (기본 행 연산을 사용하여) 행을 줄일 수 있다.

4번째 행을 추가하면 모든 코드 워드 비트(데이터 및 패리티)의 합계가 4번째 패리티 비트로 계산된다.

예를 들어, 1011은 (이 절의 시작 부분에서 비시스템적 형태의 G를 사용하여) 01100110으로 인코딩되며, 여기서 파란색 자릿수는 [7,4] 해밍 코드의 패리티 비트이며, 녹색 자릿수는 [8,4] 코드에 의해 추가된 패리티 비트다. 녹색 자릿수는 [7,4] 코드 워드의 패리티를 균등하게 만든다.

마지막으로, 최소 거리가 [7,4] 코드의 3에서 [8,4] 코드의 4로 증가했음을 알 수 있다. 따라서, 코드는 [8,4] 해밍 코드로 정의할 수 있다.

[8,4] 해밍 코드를 디코딩하려면 먼저 패리티 비트를 확인하십시오. 패리티 비트가 오류를 나타내는 경우, 단일 오류 수정([7,4] 해밍 코드)은 오류 위치를 나타내고, "오류 없음"은 패리티 비트를 나타낸다. 패리티 비트가 올바르면 단일 오류 수정은 두 오류 위치의 배타적(비트) 또는 배타적(비트)을 나타낸다. 위치가 동일하면("오류 없음") 이중 비트 오류가 발생하지 않았거나 자체 취소된 것이다. 그렇지 않으면 이중 비트 오류가 발생한 것이다.

참고 항목

메모들

^ 다음 중 Remema 12를 참조하십시오.
^ 해밍(1950), 페이지 153–154.
^ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), Mathematical Association of America, pp. 16–17, ISBN 0-88385-023-0
^ ^a ^b Moon T. 오류 수정 코딩: 수학적 방법과 알고리즘. 2005년 존 와일리 앤 선즈(Cap. 3) ISBN 978-0-471-64800-0

참조

Hamming, Richard Wesley (1950). "Error detecting and error correcting codes" (PDF). Bell System Technical Journal. 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x.
Moon, Todd K. (2005). Error Correction Coding. New Jersey: John Wiley & Sons. ISBN 978-0-471-64800-0.
MacKay, David J.C. (September 2003). Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press. ISBN 0-521-64298-1.
D.K. Bhattacharryya, S. Nandi. "An efficient class of SEC-DED-AUED codes". 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97). pp. 410–415. doi:10.1109/ISPAN.1997.645128.
"Mathematical Challenge April 2013 Error-correcting codes" (PDF). swissQuant Group Leadership Team. April 2013.

외부 링크

[1] 다음 중 Remema 12를 참조하십시오.

[FOOTNOTEHamming1950153–154-2] 해밍(1950), 페이지 153–154.

[3] Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), Mathematical Association of America, pp. 16–17, ISBN 0-88385-023-0

[Moon-4] Moon T. 오류 수정 코딩: 수학적 방법과 알고리즘. 2005년 존 와일리 앤 선즈(Cap. 3) ISBN 978-0-471-64800-0

[1]

[2]

[3]

[4]

Search