태너 그래프

코딩 이론에서, 마이클 태너(Michael Tanner)의 이름을 딴 태너(Tanner) 그래프는 코드 수정 오류를 명시하는 제약조건이나 방정식을 기술하는 데 사용되는 초당적 그래프다.코딩 이론에서 태너 그래프는 더 작은 코드로부터 더 긴 코드를 구성하기 위해 사용된다.인코더와 디코더 모두 이 그래프를 광범위하게 사용한다.

오리진스

태너 그래프는 재귀적 기법을 사용하여 작은 것들의 코드를 수정하는 더 큰 오류를 발생시키기 위한 수단으로 마이클 태너에^[1] 의해 제안되었다.그는 제품 코드에 대한 Elias의 기술을 일반화했다.

태너는 더 큰 코드를 구성하기 위해 사용되는 코드의 특정 특성과 무관하게 이러한 그래프에서 얻은 코드의 하한선을 논했다.

선형 블록 코드에 대한 태너 그래프

태너 그래프는 서브코드 노드와 디지트 노드로 분할된다.선형 블록 코드의 경우 하위 코드 노드는 패리티 검사 매트릭스 H의 행을 나타낸다.숫자 노드는 행렬 H의 열을 나타낸다.해당 행과 열의 교차점에 0이 아닌 항목이 존재하는 경우 에지는 하위 코드 노드를 자릿수 노드에 연결한다.

태너에 의해 증명된 경계

태너는 다음과 같은 한계를 증명했다.

$R{\displaystyle }$ ${\displaystyle R}$을(를) 결과 선형 코드의 비율로 하고$$, 숫자 노드의 정도는 $m{\displaystyle }$ ${\displaystyle$ m$}$이고, 하위$$ 코드 노드의 정도는 $n{\displaystyle }$ ${\displaystyle n}$으로 한다$.$ 각 하위 코드 노드가 rate r = k/n으로 선형 코드(n,k)와 연결되면 코드의 속도는 다음과 같이 제한된다.

$[\displaystyle R\geq 1-(1-r)m\,}$

Tanner 그래프 기반 방법의 계산 복잡성

이러한 재귀적 기술의 장점은 계산적으로 추적할 수 있다는 것이다.태너 그래프의 코딩 알고리즘은 무증상적으로 좋은 코드를 인정하지 않는 것으로 알려진 사이클 프리 그래프를 제외하고는 수렴이 보장되지 않지만, 실제로는 매우 효율적이다.^[2]

태너 그래프 적용

코드구성에 대한 재귀적 저복잡성 접근방식인 제모르의 디코딩 알고리즘은 태너 그래프를 기반으로 한다.

메모들

• 마이클 태너 오리지널 페이퍼
• 마이클 태너 페이지