접두사 코드

접두사 코드는 "prefix property"의 보유로 구별되는 코드 시스템의 한 유형으로, 시스템 내에 다른 코드 워드의 접두사(초기 세그먼트)인 전체 코드 워드가 없어야 한다. 고정 길이 코드의 경우 사소한 사실이기 때문에 가변 길이 코드의 고려 사항일 뿐이다.

예를 들어, 코드 단어가 {9, 55}인 코드는 접두사 속성을 가지지만, {9, 5, 59, 55}인 코드는 접두사가 "59"이고 "55"이기 때문에 그렇지 않다. 접두사 코드는 고유하게 해독 가능한 코드로, 완전하고 정확한 시퀀스를 부여하면, 수신자는 단어 사이에 특별한 마커를 요구하지 않고도 각 단어를 식별할 수 있다. 그러나 접두사 코드가 아닌 고유하게 해독 가능한 코드가 있다. 예를 들어 접두사 코드의 역방향은 여전히 고유하게 해독할 수 있지만(접미사 코드) 반드시 접두사 코드가 아니다.

접두사 코드는 접두사 없는 코드, 접두사 조건 코드 및 순간 코드라고도 한다. 허프먼 코딩은 접두사 코드를 도출하기 위한 많은 알고리즘 중 하나에 불과하지만, 허프먼 알고리즘에 의해 코드가 생성되지 않았을 때에도, 접두사 코드는 널리 "허프만 코드"라고도 불린다. 쉼표 없는 코드라는 용어는 접두사 없는 코드의^[1][2] 동의어로도 적용되기도 하지만, 대부분의 수학적 서적과 기사(예:)^[3][4]에서 쉼표 없는 코드는 접두사 코드의 하위 클래스인 자기 동기화 코드를 의미하기 위해 사용된다.

접두사 코드를 사용하면 메시지 내의 단어를 프레임으로 만들기 위해 단어 사이에 대역 외 마커나 (대안적으로) 특수 마커 없이 연결된 코드 워드의 시퀀스로 메시지를 전송할 수 있다. 수신자는 유효한 코드 단어를 형성하는 시퀀스를 반복적으로 찾아 제거함으로써 메시지를 모호하게 디코딩할 수 있다. 이는 일반적으로 접두사 속성이 결여된 코드(예: {0, 1, 10, 11): 코드 워드의 시작 부분에서 "1"을 읽는 수신자는 그것이 완전한 코드 워드인지 아니면 단지 코드 워드 "10" 또는 "11"의 접두사인지 알지 못하므로 문자열 "10"을 단일 코드 워드로 해석하거나 콩카로 해석할 수 있다."1"과 "0"을 차례로 선택하십시오.

가변 길이 허프먼 코드, 국가 통화 코드, ISBN의 국가 및 출판사 부분, UMTS W-CDMA 3G 무선 표준에서 사용되는 2차 동기화 코드, 대부분의 컴퓨터 마이크로아키텍처 명령 집합(기계 언어)은 접두사 코드다.

접두사 코드는 오류 수정 코드가 아니다. 실제로, 메시지는 먼저 접두사 코드로 압축되었다가 전송 전에 채널 코딩(오류 수정 포함)으로 다시 인코딩될 수 있다.

고유하게 해독 가능한 코드의 경우 코드 워드 길이가 동일한 접두사 코드가 있다.^[5] 크래프트의 불평등은 고유하게 해독 가능한 코드에서 가능한 코드 워드 길이의 집합을 특징으로 한다.^[6]

기술

코드의 모든 단어의 길이가 같은 경우, 코드는 고정 길이 코드, 즉 블록 코드(채널 코딩에서 고정 크기 오류 수정 코드에도 블록 코드라는 용어가 사용된다)라고 한다. 예를 들어 ISO 8859-15 글자는 항상 8비트 길이다. UTF-32/UCS-4 글자는 항상 32비트 길이다. ATM 셀은 항상 424비트(53바이트) 길다. 고정 길이 k 비트의 고정 길이 코드는 최대 ${\displaystyle 2^{}}$ k ${\$ 소스$$ 기호를 인코딩할 수 있다.

고정 길이 코드는 반드시 접두사 코드다. 가장 긴 접두사의 길이를 충족시키기 위해 고정된 기호를 더 짧은 접두사에 채움으로써 어떤 코드도 고정 길이 코드로 바꿀 수 있다. 또는 이러한 패딩 코드를 사용하여 자동 수정 및/또는 동기화를 허용하는 중복성을 도입할 수 있다. 그러나 고정 길이 인코딩은 일부 단어가 다른 단어보다 훨씬 더 전달될 가능성이 높은 상황에서 비효율적이다.

잘린 이진 부호화는 기호 n의 수가 2의 힘이 아닌 경우를 다루기 위해 고정 길이 코드의 간단한 일반화다. 소스 기호에는 길이 k와 k+1의 코드 워드가 할당되며, 여기서 k는^k 2 < n 2^k+1 2가 되도록 선택된다.

허프먼 코딩은 가변 길이 접두사 코드를 구성하기 위한 보다 정교한 기법이다. 허프먼 코딩 알고리즘은 코드 워드가 가져야 할 주파수를 입력으로 삼고, 코드 워드 길이의 가중 평균을 최소화하는 접두사 코드를 구성한다.(이것은 엔트로피를 최소화하는 것과 밀접한 관련이 있다.) 이것은 엔트로피 인코딩을 기반으로 한 무손실 데이터 압축의 한 형태다.

일부 코드는 코드 워드의 끝을 일반 데이터와 다른 특별한 "콤마" 기호로 표시한다.^[7] 이것은 문장에서 단어 사이의 공간과 다소 유사하다; 그것들은 한 단어의 끝과 다른 단어의 시작 지점을 표시한다. 모든 코드 워드가 쉼표로 끝나고 콤마가 다른 곳에 코드 워드로 나타나지 않으면 코드는 자동으로 접두사가 없는 상태가 된다. 그러나 현대의 통신 시스템은 모든 것을 "1"과 "0"의 시퀀스로 보낸다. 즉, 세 번째 기호를 추가하는 것은 비용이 많이 들고, 단어의 끝에만 사용하는 것은 비효율적일 것이다. 모스 코드는 쉼표를 가진 가변 길이 코드의 일상적인 예다. 문자 사이의 긴 멈춤과 단어 사이의 더 긴 멈춤은 사람들이 한 글자(또는 단어)가 어디에서 끝나는지 인식하도록 도와주고, 그 다음이 시작된다. 마찬가지로 피보나치 부호화는 모든 코드 워드의 끝을 표시하기 위해 "11"을 사용한다.

자가 동기화 코드는 프레임 동기화를 허용하는 접두사 코드다.

관련개념

접미사 코드는 다른 어떤 것과도 접미사가 아닌 단어의 집합이며, 동등하게 접두사 코드의 역인 단어 집합이다. 접두사 코드와 마찬가지로 문자열을 그러한 단어의 결합으로 표현하는 것은 독특하다. 비픽스 코드는 접두사 코드와 접미사 코드인 단어 집합이다.^[8] 최적 접두사 코드는 평균 길이가 최소인 접두사 코드다. 즉, 접두사 코드 C에 대해$$ $확률{\displaystyle }$ p${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle p(A_{i})$가 있는 n 기호의 알파벳을 가정한다. If C' is another prefix code and ${\displaystyle \lambda '_{i}}$ are the lengths of the codewords of C', then ${\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!}$.^[9]

현재 사용 중인 접두사 코드

접두사 코드의 예는 다음과 같다.

• 가변 길이 허프먼 코드
• 나라별 전화 번호
• 첸호 부호
• ISBN의 국가 및 출판사 부분
• UMTS W-CDMA 3G 무선 표준에 사용되는 보조 동기화 코드
• VCR Plus+ 코드
• 유니코드 변환 형식, 특히 유니코드 문자를 인코딩하기 위한 UTF-8 시스템, 즉 접두사 없는 코드와 자체 동기화 코드^[10].
• 가변 길이 수량

기술

일반적으로 사용되는 접두사 코드 구성에는 Huffman 코드와 이전 Shannon-Fano 코드 및 다음과 같은 범용 코드가 포함된다.

• 엘리아스 델타 부호화
• 엘리아스 감마 부호화
• 엘리아스 오메가 부호화
• 피보나치 부호화
• 레벤슈테인 부호화
• 단항 부호화
• 골롬 라이스 코드
• Straddling checkerboard(접두사 코드를 생성하는 간단한 암호화 기술)
• 바이너리 부호화^[11]

메모들

참조

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001.
• Elias, Peter (1975). "Universal codeword sets and representations of the integers". IEEE Trans. Inf. Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349. ISSN 0018-9448. Zbl 0298.94011.
• D.A. Huffman, "최소 재분배 코드 구축 방법", 1952년 9월 I.R.E. 절차, 페이지 1098–1102 (Huffman의 원문)
• 프로파일: 데이비드 A. 허프먼, 사이언티픽 아메리칸, 1991년 9월 페이지 54–58 (배경 이야기)
• 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개, Second Edition. MIT 프레스 앤 맥그로우 힐, 2001. ISBN 0-262-03293-7 제16.3절, 페이지 385–392.
• 이 문서에는 일반 서비스 관리 문서의 공용 도메인 자료가 포함되어 있다.

외부 링크

• 코나 맥피에 의한 코드, 트리 및 접두사 속성