분류하고자하는 k 개의 입력에 대해 n 비트의 코드를 생성하려고합니다. 이 코드의 주요 요구 사항은 오류 수정 기준입니다. 즉, 서로 다른 입력의 두 인코딩 간의 최소 쌍 거리가 최대화됩니다. 근사치가 필요하지 않으며, 계산의 용이성과 사용의 용이성 역시 중요합니다.n 비트의 크기 k 오류 수정 코드를 생성하는 알고리즘
일반적으로 n은 수십에서 수백, k입니다.
또한 k 개의 다른 n 비트 2 진 인코딩 간의 최소 해밍 거리에 대해 적절한 제한이 있습니까?
주어진 매개 변수에 대해 가장 정확한 오류 수정 코드를 찾는 문제는 매우 어렵습니다. 대략 최상의 코드조차도 어렵습니다. 그 중 일부 코드에는 괜찮은 디코딩 알고리즘이없고 다른 것들에는 디코딩 문제가 매우 까다 롭습니다.
그러나 매개 변수의 특정 범위에 대해 묻는 중입니다. 여기에서 n»k는 정확하게 이해하면 길이가 n 인 k 차원 코드가 필요합니다. (따라서 k 비트는 n 비트로 인코딩됩니다.)이 범위에서 우선, 무작위 코드는 아주 좋은 최소 거리를 가질 것입니다. 유일한 문제는 디코딩이 비실용적 인 곳에서부터 어려운 곳까지이며, 실제로 최소 거리를 계산하는 것이 쉽지 않다는 것입니다.
둘째, n> k의 사례에 대한 명시적인 코드를 원한다면 q = 2 인 BCH code을 사용하면됩니다. Wikipedia 페이지에서 설명 하듯이 BCH 코드에 대한 좋은 디코딩 알고리즘이 있습니다.
최소 해밍 거리의 상한에 대해서는 n»k 범위에서 볼륨 바운드 또는 구형 묶음이라고도하는 Hamming bound으로 시작해야합니다. 바운드의 개념은 간단하고 아름답습니다. 최소 거리가 t 인 경우 코드는 거리 마루까지 오류를 수정할 수 있습니다 ((t-1)/2). 일부 반경으로 오류를 수정할 수 있다면 해당 반경의 해밍 볼이 겹치지 않는다는 의미입니다. 반면, 가능한 단어의 총 수는 2 n입니다. 따라서 하나의 Hamming 볼 (이진수의 경우 2 진수 계수의 합계)의 점 수로 나눈다면 상한값이됩니다 오류없는 코드 워드의 수 이 한계를 넘어 설 수는 있지만 최소 거리가 멀면 쉽지 않습니다. 이 정권에서 그것은 아주 좋은 경계입니다.