표준 배열

코딩 이론에서 표준 배열(또는 Sleepian 배열)은 $q{\displaystyle {}^{}}$ n -${\displaystyle {}^{}}$k ${\$ $q$$^{$$n-k$$}}$ by$$ $q{\displaystyle {}^{}}$ k ${\$의 모든$$ 요소를 나열하는 ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ - ${\displaystyle k^{}}${n$}$의 배열이다.표준 배열은 선형 코드를 디코딩하는 데 사용된다. 즉, 수신된 벡터에 해당하는 코드 워드를 찾는 데 사용된다.

정의

[n,k]-코드의 표준 배열은 ${\displaystyle q^{}}$n - ${\displaystyle k^{}}${\$displaystyle q^{n-k}$ $by$ ${\displaystyle q^{}}$ k$${\$displaystyle q^{k}}}$ 배열이며$$, 여기서 다음을 충족한다.

1. 첫 번째 행에는 모든 코드 워드가 나열되며(극단 왼쪽에 0 코드 워드가 있음)
2. 각 행은 첫 번째 열에 코셋 리더가 있는 코셋이다.
3. i번째 행과 j번째 열에 입력된 항목은 i번째 코제트 리더와 j번째 코드 워드의 합이다.

예를 들어 [5,2]-코드 ${\displaystyle {C\mathrm{}}_{}}$ $3{\displaystyle {}_{}}$ ${\$ $$= {0, 01101, 10110, 11011}에는 다음과 같은 표준 배열이 있다.

0	01101	10110	11011
10000	11101	00110	01011
01000	00101	11110	10011
00100	01001	10010	11111
00010	01111	10100	11001
00001	01100	10111	11010
11000	10101	01110	00011
10001	11100	00111	01010

위의 것은 표준 배열에 대한 하나의 가능성일 뿐이다. 만약 00011이 무게 2의 첫 번째 코스메트 리더로 선택되었다면, 코드를 나타내는 다른 표준 배열이 구성되었을 것이다.

첫 번째 행에는 0 벡터와 C ${\displaystyle {3\mathrm{}}_{}}$ ${\$의 코드 워드가 들어 있다($$0 그 자체가 코드 워드임).또한 맨 왼쪽 열에는 먼저 무게 1의 벡터를 열거한 다음 무게 2의 벡터를 사용하는 최소 무게 열거 벡터가 들어 있다.또한 벡터 공간에서 각각의 가능한 벡터는 정확히 한 번 나타난다.

표준 배열 구성

각각의 가능한 벡터는 표준 배열에서 한 번만 나타날 수 있기 때문에 시공 시 주의해야 한다.표준 배열은 다음과 같이 생성할 수 있다.

1. 0으로 시작하는$$$C{\displaystyle }$ ${\displaystyle C}$의 코드 단어를 첫 번째 행으로 나열하십시오.
2. 배열에 없는 최소 무게의 벡터를 선택하십시오.이것을 다음 행의 첫 번째 항목으로 쓰시오.이 벡터는 '코셋 리더'로 불린다.
3. 각 열의 맨 위에 있는 코드 워드에 코셋 리더를 추가하여 행을 채우십시오.i번째 코제트 리더와 j번째 코드 워드의 합은 i번째 열 j의 항목이 된다.
4. 모든 행/코세트가 나열되고 각 벡터가 정확히 한 번 나타날 때까지 2단계와 3단계를 반복하십시오.

벡터 추가는 mod q.예를 들어, 이진 코드는 mod 2가 추가된다(비트-wise XOR 추가와 동일).${\displaystyle {예}_{}}$를 들어 $Z{\displaystyle {}_{}}$ 2 ${\$}}:$$11000 + 11011 = 00011.

다른 코스메트 리더를 선택하는 것은 약간 다르지만 동등한 표준 배열을 만들 것이며, 디코딩할 때 결과에 영향을 미치지 않을 것이다.

시공예시

$C{\displaystyle }$ ${\displaystyle C}$을(를) 이진 [4,2]-코드로$$ 설정하십시오. 즉, C = {0000, 1011, 0101, 1110.표준 배열을 구성하려면 먼저 코드 단어를 연속해서 나열하십시오.

0000

1011

0101

1110

그런 다음 사용하지 않은 최소 무게의 벡터(이 경우 중량 1)를 선택한다.이 벡터는 두 번째 행의 코제트 리더가 된다.

0000	1011	0101	1110
1000

3단계에 이어 각 코드 워드에 코제트 리더를 추가해 행을 완성한다.

0000	1011	0101	1110
1000	0011	1101	0110

그런 다음 모든 행을 완료할 때까지 2단계와 3단계를 반복하십시오.${\displaystyle {qn}^{}}$- ${\displaystyle k^{}}$= 2 ${\displaystyle 4^{}}$- 2${\displaystyle {}^{}}$= ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle 4}$ ${\displaystyle q^{n-k}=2^{4-2}=2^{2}=4}$ 행에$$ 도달하면 중지한다.

0000	1011	0101	1110
1000	0011	1101	0110
0100	1111	0001	1010
0010	1001	0111	1100

이 예에서 벡터 0001은 배열에 이미 벡터가 존재했기 때문에 최소 중량(1)의 기준을 충족하더라도 최종 행의 코제트 리더로 선택할 수 없었을 것이다.그러나 우리는 그것을 최초의 코제트 리더로 선정하고 다른 표준 배열을 만들 수 있었다.

표준 배열을 통한 디코딩

표준 배열을 사용하여 벡터를 디코딩하려면 수신된 벡터에서 오류 벡터(또는 코제트 지시선)를 빼십시오.결과는 $C{\displaystyle }$ ${\displaystyle C}$의 암호어 중 하나가 될 것이다$.$ 예를 들어, C = {0000, 1011, 0101, 1110}을 사용하고 있으며, 위의 예에서와 같이 해당 표준 배열을 구성했다고 하자.우리가 벡터 0110을 메시지로 수신하면, 우리는 표준 배열에서 그 벡터를 발견한다.그런 다음 벡터의 코제트 리더, 즉 1000을 빼서 1110의 결과를 얻는다.우리는 1110이라는 암호문을 받았다.

표준 배열을 통한 디코딩은 가장 가까운 이웃 디코딩의 한 형태다.실제로 표준 배열을 통해 해독하려면 대량의 저장 공간이 필요하며, 32개의 코드 단어가 포함된 코드는 $2개$의 ${\displaystyle {32}^{}}$ ${\$ 항목이$$ 포함된 표준 배열을 필요로 한다.신드롬 디코딩과 같은 다른 형태의 디코딩은 더 효율적이다.

표준 배열을 통해 디코딩한다고 해서 모든 벡터가 올바르게 디코딩되는 것은 아니다.벡터 1010을 수신하면 위의 표준 배열을 사용하면 코드 워드 거리 1인 1110으로 메시지를 디코딩할 수 있다.그러나 1010도 암호 1011과는 거리가 1이다.이러한 경우 일부 구현에서는 메시지를 다시 전송하도록 요구하거나 모호한 비트를 삭제로 표시하여 다음과 같은 외부 코드가 수정될 수 있다.이러한 모호성은 다른 해독 방법이 가끔 사용되는 또 다른 이유다.

참고 항목

• 선형코드

참조

• Hill, Raymond (1986). A First Course in Coding Theory. Oxford Applied Mathematics and Computing Science series. Oxford University Press. ISBN 978-0-19-853803-5.