하다마드 코드

이 기사의 리드 섹션은 기사의 길이에 비해 너무 길 수도 있다. 기사의 본문으로 일부 자료를 옮겨서 도움을 주십시요. 레이아웃 가이드 및 리드 섹션 지침을 읽고 섹션에 모든 필수 세부 정보가 포함되도록 하십시오. 기사의 토크 페이지에서 이 문제를 논의하십시오. (2020년 5월)

하다마드 코드
이름을 따서 명명됨	자크 하다마르
분류
유형	선형 블록 코드
블록 길이	${\displaystyle n=2^{k}}$
메시지 길이	$(\displaystyle k}$
등급	${\displaystyle k/2^{k}}$
거리	${\displaystyle d=2^{k-1}$
알파벳 크기	${\displaystyle 2}$
표기법	${\displaystyle [}$ ${\displaystyle {2k}^{}}$ ${\displaystyle k,}$ ${\displaystyle {2k}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}} -code$$
v t

증강 하드마드 코드
이름을 따서 명명됨	자크 하다마르
분류
유형	선형 블록 코드
블록 길이	${\displaystyle n=2^{k}}$
메시지 길이	${\displaystyle k+1}$
등급	${\displaystyle (k+1)/2^{k}}$
거리	${\displaystyle d=2^{k-1}$
알파벳 크기	${\displaystyle 2}$
표기법	${\displaystyle [}$ ${\displaystyle {2k\mathrm{}}_{}{}^{}}$ ${\displaystyle k}$+ ${\displaystyle 1}$,${\displaystyle 2^{}}$ k${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}{}_{}}$ 2 ${\$}} -code$$
v t

하다마드 코드는 자크 하다마드의 이름을 딴 오류 수정 코드로, 매우 시끄럽거나 신뢰할 수 없는 채널을 통해 메시지를 전송할 때 오류 감지 및 수정에 사용된다. 1971년, 이 코드는 NASA의 우주 탐사선 마리너 9호로부터 화성의 사진을 지구로 다시 전송하기 위해 사용되었다.^[1] 하다마드 코드는 독특한 수학적 특성 때문에 엔지니어들이 사용할 뿐만 아니라 코딩 이론, 수학, 이론 컴퓨터 과학에서도 치열하게 연구되고 있다. 하다마드 코드는 미국의 수학자 조셉 레너드 월시를 인정받아 월시 코드, 월시 계열,^[2] 월시-하다마드 코드라는^[3] 이름으로도 알려져 있다.

하다마드 코드는 이진 알파벳에 걸쳐$$ 길이 ${\displaystyle {2m}^{}}$ ${\$의 선형 코드의 예다. 불행히도 이 용어는 일부 참조에서 $메시지{\displaystyle }$ 길이 k${\displaystyle }$= ${\displaystyle m}$ ${\displaystyle k=m}$을 가정하는 반면 다른 참조에서는$$ $메시지{\displaystyle }$ 길이를 k${\displaystyle }$= ${\displaystyle m}$ + ${\displaystyle 1}$ ${\displaystyle k=m+1}$이라고 $가정$하기 때문에 다소 모호하다$.$ 이 글에서 첫 번째 경우는 하다마드 코드라고 하고, 두 번째 경우는 증강 하다마드 코드라고 한다.

하다마드 코드는 0이 아닌 각 코드 워드의 해밍 중량이 정확히 ${\displaystyle {\mathrm{2k}}^{}}$- 1 ${\$라는 점에서 독특하며$,$ 이는 코드의 거리 또한 ${\displaystyle {2k}^{}}$- ${\displaystyle 1^{}}$ ${\$임을 의미한다$.$ 블록 코드의 표준 코딩 이론 표기법에서, 하다마드 코드는${\displaystyle }$[${\displaystyle {2k}^{}}$ ${\displaystyle k,}$ ${\displaystyle {\mathrm{2k}}^{}}$, 2 - 1${\displaystyle {}^{}{}_{}}$이다.${\displaystyle [2^{k},k,2^{k-1}]_{2$}} -코드$$, 즉 이진 알파벳에 대한 선형 코드로서 블록 길이 ${\displaystyle {2k}^{}}$ ${\$ 2$^{$$k$$\}\},$ 메시지 길이(또는 치수) $k{\displaystyle }$ ${\displaysty k$ 최소 거리 ${\displaystyle 2k\mathrm{}{}^{}}$/ 2 ${\displaystystystyleyle$ 2k$}/2$ 블록 길이는 메시지 길이에 비해 매우 크지만, 다른 한편으로는 극도로 시끄러운 상황에서도 오류를 수정할 수 있다.

증강된 하다마드 코드는 Hadamard 코드의 약간 개선된 버전으로$,{\displaystyle }$ [${\displaystyle {2k}^{}}$ ${\displaystyle k}$+ ${\displaystyle 1}$,${\displaystyle }$2 ${\displaystyle k^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$$displaystyle$$[2$$^{$$k},k+1$,2$^{k-1}]_$${$2$}}$ -code로서$$ $상대적$인 거리를 1$2$로 유지하면서 약간 더 높은 비율을 가지고 있어 실용적으로 선호되고 있다$.$ 의사소통 이론에서 이것은 간단히 하다마드 코드라고 불리며 이진 알파벳에 대한 리드-뮬러 코드의 첫 번째 순서와 같다.^[4]

보통 하다마드 코드는 실베스터가 하다마드 매트릭스를 구축한 것을 기본으로 하지만, 반드시 실베스터 타입이 아닌 임의의 하다마드 매트릭스로 구축한 코드를 가리키는 데에도 "하다마드 코드'라는 용어가 사용된다. 일반적으로 그러한 코드는 선형적이지 않다. 그러한 암호는 1959년 라즈 찬드라 보세와 샤라드찬드라 샨카르 슈리칸데에 의해 처음 만들어졌다.^[5] n이 Hadamard 행렬의 크기인 경우, 코드에는 파라미터$({\displaystyle n,}$ ${\displaystyle 2n\mathrm{},}$ ${\displaystyle n}$/${\displaystyle {}_{}}$2 ) ${\displaystyle {2\mathrm{}}_{}}$ ${\$2}}개가 있는데$,$ 이는 2n 코드 워드의 블록 길이 n과 최소 거리 n/2를 갖는 불필요한 선형의 이진 코드라는 뜻이다. 아래에 기술된 구성 및 디코딩 방식은 일반 n에 적용되지만, 선형성의 특성과 리드-멀러 코드로 식별하는 것은 n이 2의 검정력이어야 하며, 하다마드 매트릭스는 실베스터의 방법에 의해 구성된 매트릭스와 동일해야 한다.

하다마드 코드는 로컬로 해독 가능한 코드로, 수신된 단어의 극히 일부분만 보면서도 원본 메시지의 일부를 높은 확률로 복구할 수 있는 방법을 제공한다. 이것은 계산 복잡성 이론과 특히 확률적으로 확인할 수 있는 증명 설계에 응용을 야기한다. 하다마드 코드의 상대적 거리가 1/2이기 때문에, 보통은 1/4 정도의 오차로부터 회복되기를 바랄 뿐이다. 그러나 목록 디코딩을 사용하면 수신된 워드의 비트 중$$ $1{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \mathrm{2개}}$ -$$bits {\$displaystyle {\frac {1}{1}{$2}}-\$엡실론 }$보다 적은 수의 가능한 후보 메시지의 짧은 목록을 계산할 수 있다.

코드분할다중접속(CDMA) 통신에서 하다마드 코드는 월시 코드(Walsh Code)라고 하며, 개별 통신 채널을 정의하는 데 사용된다. CDMA 문서에서는 코드 단어를 "코드"라고 부르는 것이 보통이다. 각 사용자는 다른 코드 워드 또는 "코드"를 사용하여 신호를 수정한다. 월시 코드 워드는 수학적으로 직교하기 때문에, 월시 인코딩 신호는 CDMA 지원 이동 단말기에 무작위 노이즈로 나타난다. 단자는 수신 신호를 인코딩하는 데 사용되는 것과 동일한 코드 워드를 사용하지 않는 한 말이다.^[6]

역사

Hadamard code는 문헌에서 이 코드에 가장 일반적으로 사용되는 이름이다. 그러나 현대용에서는 이러한 오류 수정 코드를 월시-하다마드 코드라고 한다.

여기에는 다음과 같은 이유가 있다.

자크 하다마드는 직접 코드를 발명한 것은 아니지만, 1940년대에 최초의 오류 수정 코드인 해밍 코드가 개발되기 훨씬 전인 1893년경에 하다마드 행렬을 정의했다.

하다마드 코드는 하다마드 매트릭스에 기초하고 있으며, 여기서 사용할 수 있는 다양한 하다마드 매트릭스가 많지만, 일반적으로는 실베스터의 하다마드 매트릭스 구축만이 하다마드 코드의 암호어를 얻기 위해 사용된다.

James Joseph Sylvester는 1867년에 Hadamard 행렬의 건설을 개발했는데, 이것은 실제로 Hadamard 행렬에 대한 Hadamard의 작업을 능가한다. 따라서 하다마드 코드라는 명칭은 논란이 되고 있으며 때로는 미국의 수학자 조셉 레너드 월시를 기리며 월시 코드라고 불리기도 한다.

1971년 Mariner 9 임무 동안 사진 전송 오류를 수정하기 위해 증강된 Hadamard 코드가 사용되었다. 이 임무 동안 사용된 데이터 단어는 64개의 그레이스케일 값을 나타내는 6비트 길이였습니다.

당시 송신기 정렬 품질의 한계 때문에(도플러 추적 루프 문제로 인해) 최대 유용 데이터 길이는 약 30비트였다. 반복 코드를 사용하는 대신, [32, 6, 16] Hadamard 코드가 사용되었다.

단어당 최대 7비트 오류는 이 방법을 사용하여 수정할 수 있다. 5반복 코드에 비해 이 하다마드 코드의 속성을 교정하는 오류는 훨씬 낫지만 그 속도는 비교가 안 된다. 효율적인 디코딩 알고리즘은 이 코드를 사용하기로 결정하는데 중요한 요소였다.

사용된 회로는 "그린 머신"이라고 불렸다. 디코딩 속도를 3배 높일 수 있는 빠른 푸리에 변환을 채용했다. 1990년대 이후 우주 프로그램에 의한 이 코드의 사용은 거의 중단되었고, NASA 딥 스페이스 네트워크는 26m 이상의 접시에 대해 이 오류 수정 계획을 지원하지 않는다.

시공

모든 Hadamard 코드는 Hadamard 매트릭스에 기반을 두고 있지만, 그 구조는 다른 과학 분야, 작가, 그리고 용도에 따라 미묘한 방식으로 다르다. 데이터 전송에 코드를 사용하는 엔지니어들과 코드의 극단적 특성을 분석하는 코딩 이론가들은 일반적으로 코드의 속도가 수학적으로 약간 덜 우아해지는 것을 의미하더라도 가능한 한 높기를 원한다.

반면에 이론 컴퓨터 과학에서 Hadamard 코드의 많은 적용의 경우 최적 속도를 달성하는 것이 그리 중요하지 않으며, 따라서 보다 우아하게 분석할 수 있기 때문에 Hadamard 코드의 단순한 구성이 선호된다.

내부 제품을 이용한 시공

길이 $k{\displaystyle }$ ${\displaystyle k}$의 이진 메시지 $x{\displaystyle }$ $,$\}$k}{{0,1\}^{k}}$이(${\displaystyle 가}$) 주어졌을 때, Hadamard 코드는 메시지를 코드 워드 ${\displaystyle \text{Had}}$( x${\displaystyle }$) ${\displaystyle {\text}$로 인코딩한다$.$인코딩 함수를 사용하여$$ ${\displaystyle \text{had}}$$}(x):$${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$→${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle {2^{}}^{}}$ ${\displaystyle {k{\mathrm{}}^{}}^{}}$. ${\displaystyle {\text{$$had}:\{0,1\}^{k}\{0,1\}^{2^{k}}}}}}$$$ ${\displaystyle 이}$ 함수는 다음과 같이 정의된 내부 제품 $x$ x${\displaystyle }$, ${\displaystyle y}$ ${\displaystyle ⟩}$ ${\displaystyle \langle$ x$,y\rangele$${\displaystyle \},}$ y${\displaystyle }$} {${\displaystyle 0}$,1${\displaystyle \backslash \}\mathrm{k}}$, $\$ x$,y\in \{0,1\}^{k}}}}$를 사용한다$.$

${\displaystyle \langle x,y\langle =\sum _{i=1}^{k}x_{i}y_{i}\\bmod {\}2}}\,}$

그런 다음 $x{\displaystyle }$ ${\displaystyle x}$의 Hadamard 인코딩을 $x{\displaystyle }$ ${\displaystyle x}$이(가) 있는 모든 내부 제품의 시퀀스로 정의한다$.$

${\displaystyle {\text{had}}(x)={\Big(}\langle x,y\rangele {\Big )}_{{0,1\}^{k}}}}}}$

위에서 언급한 바와 같이, 증강된 하다마드 코드는 그 자체가 다소 낭비적이기 때문에 실제로 사용되고 있다. $왜냐하면{\displaystyle }$, y ${\displaystyle y}$의 첫 번째 비트가 0이고$$ $y{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle 0}$ ${\displaystyle y_{1}=0}$이면$,$ 내부 제품에는 ${\displaystyle {x\mathrm{}}_{}}$ 1 ${\$에 대한 정보가 전혀 포함되어 있지 않기 때문에 코드 워드의 위치에서만$$ x ${\displaystystyle$ x$}$를 완전히 디코딩할 수 없기 때문이다. 한편, 코드 ${\displaystyle {워드}_{}}$가 y${\displaystyle {}_{}1}$ = 1 ${\displaystyle y_{1}=1}$의 위치로 제한되었을 때$,$ $여전히{\displaystyle }$ x ${\displaystyle$ x$}$을(를) 완전히 디코딩할 수 있다$.$ 따라서 이러한 위치로 Hadamard 코드를 제한하는 것이 타당하며, 이는 $x{\displaystyle }$ ${\displaysty x$의 증강된 Hadamard 인코딩을 발생시킨다. ${\$$$$had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{{1\}\times \{0,1\}^{k-1$

제너레이터 매트릭스를 이용한 시공

Hadamard 코드는 선형 코드로서 모든 선형 코드는 제너레이터 매트릭스 $G{\displaystyle }$ ${\displaystyle G}$에 의해 생성될 수 있다$.$ ${\displaystyle \text{Had}}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle x}$ ${\displaystyle \cdot }$ G ${\displaystyle {\text{$$Had}}(x)=x\cdot G}$ holds for all ${\displaystyle x\in \{0,1\}^{k}}$, where the message ${\displaystyle x}$ is viewed as a row vector and the vector-matrix product is understood in the vector space over the finite field ${\displaystyle \mathbb {F} _{2}}$. In particular, an equivalent way to write t$Hadamard{\displaystyle }$ 코드에 대한 내부 제품 정의는 $길이가 k$$displaystyle$ k}인 모든 문자열 y ${\$displaystyle $y}$로 구성된 열을 사용하는 제너레이터 매트릭스를 사용하여 발생한다.

${\displaystyle G={\begin{pmatrix}\uparrow &&\uparrow &&\uparrow &&&\uparrow \\\\y_{1}&}{2^{k}\\downarrow &&\downarrow \end{pmatrix}},}$

여기서 $y{\displaystyle {}_{}}$ ${\displaystyle i_{}\in \{0}$, ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$ ${\$는 사전순으로 i ${\displaystyle$ i$}$ -th$$ 이진 벡터다$$. 예를 들어 치수 $k{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle k=3}$의 Hadamard 코드에 대한 제너레이터 매트릭스는 다음과$$ 같다.

${\displaystyle G={\begin{bmatrix}0&0&0&0&1&1&1&1\\0&0&1&1&1&1&#0&1&#1&#1&#1&#1&#1&#1&#1&#end{bmatrix}}}}.}$

행렬 $G{\displaystyle }$ ${\displaystyle G}$은$({\displaystyle }$는) a (${\displaystyle k}$ ${\displaystyle \times }$ ${\displaystyle {2k}^{}}$) ${\displaystyle(k\times$ 2$^{k}})$ -매트릭스이며$$ 선형 연산자 ${\displaystyle \text{Had}}$: ${\displaystyle 0,}$ ${\displaystyle 1^{}}$ %, ${\displaystyle {1^{}}^{}}$ ${\displaystyle {}^{}}$ k${\displaystyle {}^{}}$→${\displaystyle 1{}^{}}$ ${\displaystyle {2{\mathrm{}}^{}}^{}}$ k ${\$ {\text${$$had}:\{0,1\}^{k}\{0,1\}^{2^{$k$\}\}\}\}\}\}.$

증강된 Hadamard 코드의 제너레이터 매트릭스는 매트릭스 $G{\displaystyle }$ ${\displaystyle G}$를 첫 번째 항목이 하나인 열로 제한하여 얻는다$$. 예를 들어 치수 $k{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle k=3}$의 증강 Hadamard 코드에 대한 제너레이터 매트릭스는 다음과 같다$$.

${\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1\\0&1&1\end{bmatrix}}.}$

그런 다음 ${\displaystyle \text{pHad}}$:${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$→${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle {2{\mathrm{}}^{}}^{}}$ ${\displaystyle {k^{}}^{}}$- ${\displaystyle {1^{}}^{}}$ ${\$$had}:\{0,1\}^{k}\$to$\{0,$1\}^{2$^{k-1}}$는 pHad${\displaystyle }$(${\displaystyle x}$ ) = x${\displaystyle }$′ ${\displaystyle {}^{}}$ $′$ {\$displaystyle${\$text{p$$)$로 선형 매핑된 것이다$$.$had}}(x)=x\cdot$ G$\text{'}\}.$

일반 $k{\displaystyle }$ ${\displaystyle k}$의 경우$,$ 증강 Hadamard 코드의 제너레이터 매트릭스는 길이 ${\displaystyle {2k}^{}}$- ${\displaystyle 1^{}}$ ${\$ 2$^{k-1-k$$}$ 및 치수$$ ${\displaystyle {2k}^{}}$- ${\displaystyle \mathrm{1k}}$ ${\displaystyle 2^{k-1-k}$의 확장 해밍 코드에 대한 패리티 검사 매트릭스다$.$ 따라서 Hadamard 코드를 정의하는 다른 방법은 패리티 체크 매트릭스 측면에서 볼 수 있다. 즉, Hadamard 코드의 패리티 체크 매트릭스는 해밍 코드의 제너레이터 매트릭스와 동일하다.

일반 Hadamard 매트릭스를 이용한 시공

Hadamard 코드는 n-by-n Hadamard 매트릭스 H에서 얻는다. 특히 코드의 2n 코드 워드는 H 행과 -H 행이다. {0,1} 알파벳을 통해 코드를 얻으려면 매핑 -1 ↦ 1, 1 ↦ 0 또는 동등하게 x ↦(1 - x)/2가 매트릭스 요소에 적용된다. 코드의 최소 거리가 n/2인 것은 Hadamard 행렬의 정의 속성(즉, 행이 상호 직교라는 것)에서 비롯된다. 이것은 Hadamard 행렬의 두 개의 뚜렷한 행이 정확히 n/2 위치에서 다르다는 것을 의미하며, 행의 부정이 직교성에 영향을 미치지 않기 때문에 행이 일치하는 경우를 제외하고 n/2 위치에서도 H의 행이 -H의 어떤 행과 다르다는 것을 의미한다.

$n{\displaystyle }$= ${\displaystyle {2k}^{}}$- ${\displaystyle 1^{}}$ ${\$와 함께 위의 증강된 Hadamard 코드를 얻으려면 선택한 Hadamard 매트릭스 H가 Sylvester 유형이어야 하며, 이는 ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ (${\displaystyle \mathrm{2n}}$)${\displaystyle }$= ${\displaysty \log _{2}(2n)=k}$의 메시지 길이를 발생시킨다$.$

거리

코드의 거리는 두 개의 구별되는 코드 단어 사이의 최소 해밍 거리, 즉 두 개의 구별되는 코드 단어가 다른 위치의 최소 수입니다. 월시-하다마드 코드는 선형 코드이므로 거리는 모든 비 0 코드 단어 중 최소 해밍 중량과 동일하다. 월시-하다마드 코드의 모든 비제로 코드 워드는 다음 인수에 의해$$ 정확히 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle k^{}}$- ${\displaystyle 1^{}}$ ${\$ 2$^{k-1}$의 해밍 중량을 가진다.

$x{\displaystyle \in \{0\},}$ ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ k ${\$\{$0,1\}^{k}}}$을(를) 0이 아닌 메시지로$$ 두십시오. 그러면 다음 값은 코드 워드에서 1과 동일한 위치의 비율과 정확히 동일하다.

${\displaystyle \Pr_{y\in \{0,1\}^{k}}}{\big [}({\text{})had}(x)_{y}=1{\big ]}=\Pr_{y\in \{0,1\}^{k}}{\big [}\big [}\langle x,y\rangle =1\big ]}\,}$

후자의 값이 정확히 $1{\displaystyle \mathrm{}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle$ 1/$2}$이라는 사실을 난수 서브섬 원리라고 한다$$. 사실인지 확인하려면 일반성의 손실 없이 ${\displaystyle \mathrm{x}}$ ${\displaystyle {1\mathrm{}}_{}}$= 1 ${\displaystyle x_{1}=1}$을(를) 가정하십시오$.$ Then, when conditioned on the values of ${\displaystyle y_{2},\dots ,y_{k}}$, the event is equivalent to ${\displaystyle y_{1}\cdot x_{1}=b}$ for some ${\displaystyle b\in \{0,1\}}$ depending on ${\displaystyle x_{2},\dots ,x_{k}}$ and ${\displaystyle y_2}$${\displaystyle {}_{},}$, ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ ${\displaystyle y}$ ${\displaystyle {1\mathrm{}}_{}}$= b ${\displaystyle y_{1}=b}$이 발생할 확률은 $정확히{\displaystyle \mathrm{}}$ ${\displaystyle 1\mathrm{}}$/ 2 {\$displaystyle 1/2}$이므로$,$ 실제로 Hadamard 코드의 0이 아닌 모든 코드 워드는 상대 해밍 $가중치{\displaystyle \mathrm{}}$ 1${\displaystyle }$/ 2 ${\displaystyle 1$/$2$$}$을 가지고 있으며$,$ 따라서 상대적 $거리$는 1${\displaystyle /2\mathrm{}}${\$displaystystytyle$ 1/$2}$이다$.$

증강된 하다마드 코드의 상대적 $거리$도${\displaystyle 1\mathrm{}}$ / 2 ${\displaystyle 1/2}$이지만, $모든{\displaystyle \mathrm{}}$ 1 ${\displaystyle$ ${\displaystyle {{1k}^{}}^{}}$ $-$ ${\displaystyle {1^{}}^{}}$ ${\$가 아우스트맨의 코드 워드이기$$ 때문에$$ 더 이상 0이 아닌 모든 코드 워드의 중량이 $정확히{\displaystyle \mathrm{}}$1/${\displaystyle 2\mathrm{}}$ ${\displaystytype$ 1/$2}$인 속성은 없다.테드 하다마드 코드. 벡터 $x{\displaystyle }$= ${\displaystyle {10k}^{}}$- ${\displaystyle 1^{}}$ ${\$인코딩은$$ ${\displaystyle \text{pHad}({10k}^{}}$- ${\displaystyle 1^{}}$)${\displaystyle }$= ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {{\mathrm{2k}}^{}}^{}}$- 1 ${\$이기 때문이다.$had}}}(10^{k-1}=1^{2^{k-1$ $더욱이{\displaystyle }$ x ${\displaystyle x}$가 0이 아니고$$ 벡터 ${\displaystyle {\mathrm{10k}}^{}}$- 1 ${\$이 아닐 때마다 임의의 서브섬 원리가 다시 적용되며 ${\displaystyle \text{had}}$(${\displaystyle x}$) ${\displaystystyle {\cext${\}의 상대중량이 된다$.$$had}(x)}$은(는) 정확히 $1{\displaystyle \mathrm{}}$/ 2 ${\displaystyle$1$/2}$ 입니다$.$

국소 해독성

국지적으로 해독 가능한 코드는 수신된 단어의 작은 부분만 보고 원본 메시지를 높은 확률로 복구할 수 있는 코드다.

$수신$된 워드의 q {\displaystyle $q}$비트를$$ 확인하여 메시지 $비트$인 ${\displaystyle x_{}}$ i ${\$를 복구할 수 있는 경우 코드는 $q{\displaystyle }$ ${\$displaystyle $q}$ -query$$ 로컬로 해독할 수 있다$.$ More formally, a code, ${\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}$, is ${\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}$-locally decodable, if there exists a probabilistic decoder, ${\displaystyle D:\{0,1\}^{n}\rightarrow$$\{0,1\}^{k$와 같은 (참고: $\Delta {\displaystyle \mathrm{}(x}$, ${\displaystyle y}$) ${\displaystyle \Delta(x,y)}$는 벡터 $x{\displaystyle }$ ${\displaystyle x}$와 $y{\displaystyle }$ ${\displaysty y}$ 사이의 해밍 거리를 나타낸다$$$).$

${\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}}$, ${\displaystyle \Delta (y,C(x))\leq \delta n}$ implies that ${\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\$$[k]}에$

Theorem 1: The Walsh–Hadamard code is ${\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}$-locally decodable for all ${\displaystyle 0\leq \delta \leq {\frac {1}{4}}}$.

Lemma 1: 모든 코드 워드의 $경우{\displaystyle }$, $C{\displaystyle }$ ${\displaystyle C},$C ${\displaystyle i_{}}$+ ${\displaystyle c_{}}$ ${\displaystyle {}_{}}$= ${\displaystyle c_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle j_{}}$ = c + j ${\$}에$$ c ${\$displaystystyle $c}$$}}=$${\displaystyle {c\_}_{}}$${$$i+j$$\},$ ${\displaystyle {}_{}}$서 c ${\displaystyle i_{}{}_{}}$, c ${\$${\displaystyle {c\_}_{}}$${j}$는 각각$$ $위치{\displaystyle }$ i ${\displaystyle \{\backslash }$$displaystyle$ $i$$}$와 $j{\displaystyle }$ ${\$${\displaystyle i}$$+$$}$에서 $c{\displaystyle }$ ${\displaystystyle$ c$}$에 있는 비트를$$$$ 나타낸다$.$

보조정리증서1

---

$Let{\displaystyle }$ C${\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle c}$= (${\displaystyle {c\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{2n}{}^{}}_{}}$- 1${\displaystyle {}_{}}$) ${\displaystyle C(x)=c=(c_{0},\dots, c_{2^{n}-1}}}}$는 $메시지{\displaystyle }$ $x{\displaystyle }$ ${\displaystyle$ x}에 해당하는$$ C ${\displaystystyle C}$의 코드 워드가 된다$$$.$

Let ${\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}$ be the generator matrix of ${\displaystyle C}$.

정의상 $c{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle x}$ $⋅$ g $i$ ${\$${\displaystyle x}$$\$${\displaystyle {}_{}}$ $g_{i$ 이로부터 $c{\displaystyle {}_{}}$ ${\displaystyle i_{}}$+ ${\displaystyle c_{}}$= x ${\displaystyle \cdot }$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$+ ${\displaystyle {}_{}}$ ${\displaystyle \cdot }$ ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$= ${\displaystyle x}$ ⋅ ( g ${\displaystyle i_{}}$+ g ) = x ${\displaystyle \cdot }$(${\displaystyle {}_{}}$ + $){i}+c_{j$.$}}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j$ $G{\displaystyle }$ ${\$$displaystyle$ $G$ $=$ ${\displaystyle \mathrm{따라서}}$ 대체에 의해 ${\displaystyle c_{}}$ i${\displaystyle {}_{}}$+ c ${\displaystyle j_{}}$= x ${\displaystyle \cdot }$ ${\displaystyle g_{}}$ ${\displaystyle {}_{}}$+ j${\displaystyle {}_{}}$= c ${\displaystyle i_{}}$+ ${\displaystyle j_{}}$ = c + j ${\$.$}}=x\cdot g_{i+j}=c_{i+j$

정리증서1길

---

정리 1을 증명하기 위해 우리는 해독 알고리즘을 구성하고 그것의 정확성을 증명할 것이다.

알고리즘.

입력: 수신 단어 $y{\displaystyle }$=${\displaystyle }$( ${\displaystyle {y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$…${\displaystyle }$, y ${\displaystyle {\mathrm{2n}{}^{}}_{}}$- 1${\displaystyle {}_{}}$) ${\displaystyle y=(y_{0},\dots,y_{2^{n}-1}}$

${\displaystyle 각}$ $i{\displaystyle \in \{}$ ${\displaystyle 1}$,${\displaystyle }$…${\displaystyle }$, n ${\displaystyle \}}$ ${\displaystyle i\in \{1,\dots ,n\}$:

1. $j{\displaystyle }$ ${\displaystyle \in \{0}$,${\displaystyle }$…${\displaystyle {2n}^{}}$- ${\displaystyle 1\}}$ ${\displaystyle j\in \{0,\dots,2^{n}-1\}}$을(를) 무작위로 균일하게$$ 선택한다.
2. Pick ${\displaystyle k\in \{0,\dots ,2^{n}-1\}}$ such that ${\displaystyle j+k=e_{i}}$, where ${\displaystyle e_{i}}$ is the ${\displaystyle i}$-th standard basis vector and ${\displaystyle j+k}$ is the bitwise xor of ${\displaystyle j}$ and ${\$$디스플레이$ 스타일 $k}$.
3. ${\displaystyle x_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$+ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$y_${k$

출력: 메시지 $x{\displaystyle }$=${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, x ${\displaystyle n_{}}$) ${\displaystyle x=(x_{1},\dots ,x_{n}}}$

정확성 증명

모든 메시지의 경우, $x{\displaystyle }$ ${\displaystyle x}$및 $수신$ $단어{\displaystyle }$y {\$displaystyle y}$이(가) $최대$ $\Delta {\displaystyle }$ ${\displaystyle$ \$delta }$ 비트의 c$$${\displaystyle }$= C$(x)$와 $다르며$, x i ${\$displaystyty $x_{$는 $1{\displaystyle \frac{\mathrm{}}{}}$ +${\displaystyle }$(1 2${\displaystyle )}$의 확률로 디코딩할 수 있다$$.${\displaystyle -}$ ${\displaystyle 2}$ ${\displaystyle \Delta }$) ${\displaystyle {\frac {1}{$1}:{$2}}+({\frac {1}{2}}-2\property )}$.

보조정리 방법 1, $c{\displaystyle {}_{}}$ ${\displaystyle j_{}}$+ c ${\displaystyle k_{}}$= c ${\displaystyle j_{}}$= ${\displaystyle x{}_{}\cdot }$ ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$+ ${\displaystyle k{}_{}}$= x ${\displaystyle \cdot }$ ${\displaystyle e_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ = x i = x i ${\$k_{k_{$k$}$}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}$. Since ${\displaystyle j}$ and ${\displaystyle k}$ are picked uniformly, the probability that ${\displaystyle y_{j}\not =c_{j}}$ is at most ${\displaystyle \delta }$. Similarly, the probability that ${\displaystyle y_{k}\not =c_{k}}$$$ ${\displaystyle {최대}_{}}$ ${\$$displaystyle$ $\delta$$$$\}.$ 조합 바인딩에 의해 $y{\displaystyle {}_{}}$ j ${\$ $y_{j}$ 또는$$ ${\displaystyle y_{}}$ $k{\displaystyle {}_{}}$ ${\displaystyle c}$의 해당 비트와 일치하지 않을$$ 확률은 최대$$ $2{\displaystyle \mathrm{}}$ ${\displaystystyle$ $2\delta$ $\}.$ 만약 ${\displaystyle {yj}_{}}$ ${\$dism$$.${\displaystyle k_{}}$ ${\$는 $c{\displaystyle }$ ${\displaystyle c}$에 해당하며$,$ 이어 보조정리 1이 적용되므로 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 적절한 값이 계산된다$$. Therefore, the probability ${\displaystyle x_{i}}$ is decoded properly is at least ${\displaystyle 1-2\delta }$. Therefore, ${\displaystyle \epsilon ={\frac {1}{2}}-2\delta }$ and for ${\displaystyle \epsilon }$ to be positive, ${\displaystyle 0\leq \delta \leq {\frac$${1}{4}}}$.

따라서 월시-하다마드 코드는${\displaystyle }$($2{\displaystyle \mathrm{}}$,${\displaystyle }$${\displaystyle \Delta \frac{\mathrm{}}{},}$${\displaystyle \frac{1}{}}$ $2$- ${\displaystyle 2}$ $){\delta,{\frac {1}{$1}{$2}}-2\delta )}$ 로컬로$$ 0${\displaystyle \Delta }$ ${\displaystyle \frac{\mathrm{\Delta }}{}}$ 1 4 ${\\displaystyle$ 0\$leq \delq \frac{1}{4}}}$에 대해 해독할 수 있다$.$

최적성

k ≤ 7의 경우 선형 Hadamard 코드는 최소 거리의 관점에서 최적으로 입증되었다.^[7]

참고 항목

• Zadoff-Chu 시퀀스 — 월시-하다마드 코드보다 개선

참조

추가 읽기

• Rudra, Atri. "Hamming code and Hamming bound" (PDF). Lecture notes.
• Rudolph, Dietmar; Rudolph, Matthias (2011-04-12). "46.4. Hadamard– oder Walsh–Codes". Modulationsverfahren (PDF) (in German). Cottbus, Germany: Brandenburg University of Technology (BTU). p. 214. Archived (PDF) from the original on 2021-06-16. Retrieved 2021-06-14. (xiv+일반 페이지)