1. 트렐리스 도 / 트렐리스 격자도 (Trellis Diagram)
ㅇ 가로 축(시간), 세로 축(부호기 상태)로 구성된, 격자 형태의 상태 천이 그래프
ㅇ 길쌈 부호의 표현 방법 중 하나임
- 나뭇가지도의 시간적 반복성을 이용하여 축약시킨 표현 형태
. 나뭇가지도에서 동일 상태로 수렴하는 경로들을 하나의 노드로 병합함으로써 축약 가능
* [참고] ☞ 길쌈 부호 표현 (나뭇가지도,트렐리스도 포함 6가지) 참조
2. 트렐리스도, 나뭇가지도 간의 비교
ㅇ 나뭇가지도 (Tree Diagram)
- 전체 가능한 입력열을 모두 펼쳐 표현
- 경로 수가 시간 경과에 따라 계속 증가 (시간에 따라 지수적 증가)
- 복호 알고리즘 적용에는 비실용적 (경로 수 폭발)
ㅇ 트렐리스도 (Trellis Diagram)
- 동일 상태를 병합하여 반복 구조로 축약 표현
- 경로 수가, 상태 수로써 일정하게 유지됨
- 복호 알고리즘 적용에 유리함 (비터비 알고리즘 직접 적용 가능)
3. 트렐리스도의 특징
ㅇ 시간축 방향으로 동일 구조가 반복됨
- 즉, 시불변 구조 : 동일 패턴이 시간에 따라 반복
ㅇ 부호기의 메모리(memory) 특성이 잘 드러남
ㅇ 상태 천이 및 출력 관계를 시각적으로 표현 가능
ㅇ 최적 복호 알고리즘 구현에 적합
ㅇ 상태 수(= 2ν)에 따라 복잡도가 결정됨
— 상태 수가 많을수록 표현력 ↑, 그러나 비터비 복호 연산량도 비례하여 증가
4. 트렐리스도의 구성 요소
ㅇ 노드 (Node) : 각 시점의 부호기 상태(state)
ㅇ 가지 (Branch) : 하나의 시간 단계의 상태 천이로,
- 전이를 유발한 입력 비트와 그에 대응하는 출력 심볼이 함께 표시됨
ㅇ 경로 (Path) : 시간에 따른 상태 변화 과정
- 하나의 경로가 하나의 입력열/코드워드에 대응됨
. 하나의 코드워드는, 각 노드를 지날 때, 하나의 심볼을 출력하는 경로를 나타냄
ㅇ 상태 (State : encoder state)
- 부호기(Shift Register)의 현재 내용으로 정의되는 부호기의 내부 조건
. 메모리 차수 ν → 상태 수 = 2ν → 각 시각에 2ν개 노드 수
. 상태가 많을수록 자유 유클리드 거리 ↑, 복호 복잡도 ↑
. 트렐리스도의 각 행이 하나의 상태에 대응
* 例) 만일, ν = 2이면, 상태 집합 = {00, 01, 10, 11}
. 시각 t에서, 상태 s와 입력 비트 u가 결정되면, 출력 심볼과 다음 상태 s'가 유일하게 결정됨
5. 트렐리스도의 활용
ㅇ 활용
- 비터비 알고리즘에 의한 최대우도 복호(ML Decoding)
- 경로 메트릭(Path Metric) 계산
- 생존 경로(Survivor Path) 선택
ㅇ 분석 도구로서의 활용
- 오류 사건(error event) 분석
- 자유 유클리드 거리(dfree) 산출