반복적 비테르비 디코딩

Iterative Viterbi decoding

반복적 Viterbi 디코딩은 관측치 O = {o1, ..., on}의 부분 S를 m 상태로 지정된 숨겨진 Markov 모델 M에 의해 생성되는 가장 높은 평균 확률(즉, S의 길이에 따라 크기가 조정되는 확률)을 나타내는 알고리즘이다.알고리즘은 내부 단계로 수정된 비테르비 알고리즘을 사용한다.

확장 확률 측정은 존 S. 브릴이 처음 제안했다.이 문제를 해결하기 위한 초기 알고리즘인 슬라이딩 윈도우가 Jay G. Wilpon 외, 1989년에 제안되었으며, 지속적인 비용 T = mn2/2가 제시되었다.

더 빠른 알고리즘은 Viterbi 알고리즘에 대한 호출의 반복으로 구성되며, 수렴될 때까지 필러 점수를 재추정한다.

알고리즘

기본(최적화되지 않은) 버전, t의 일부 부속품에서 정규화된 가장 작은 거리로 시퀀스 s를 찾는 것은 다음과 같다.

// input is placed in observation s[1..n], template t[1..m], // and [[distance matrix]] d[1..n,1..m] // remaining elements in matrices are solely for internal computations (int, int, int) AverageSubmatchDistance(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0..(m+1)]) {     // score, subsequence start, subsequence end     declare int e, B, E     t'[0] := t'[m+1] := s'[0] := s'[n+1] := 'e'      e := random()     do         e' := e  for i := 1 to n do d'[i,0] := d'[i,m+1] := e  (e, B, E)  := ViterbiDistance(s', t', d')         e := e/(E-B+1)     until (e == e')      return (e, B, E) }

ViterbiDistance() 절차는 t와 선택된 엔트리(B) 및 출구(E) 점수에 대한 튜플(e, B, E)을 반환한다. "B"와 "E"는 Viterbi에 대한 간단한 수정을 사용하여 기록해야 한다.

앙투안 로젠노프가 제안한 CYK 표에 적용할 수 있는 수정은 초기 매트릭스 d의 모든 요소에서 e를 빼는 것으로 구성된다.

참조

  • Silaghi, M, "평균 관측 확률 기준을 사용하여 HM과 일치하는 Spotting Sequence"와 Keyword Spotting, 2005년 AAAI,
  • Rozennop, Antoine, Silaghi, Marius; 2001년 TALN 2001, "알고리즘 드 데 디코다지 드 트레일리스 셀론 르 크리테 드 코트 모옌 붓 라 정찰 드 라 가석방"

추가 읽기

  • Li, Huan-Bang; Kohno, Ryuji (2006). An Efficient Code Structure of Block Coded Modulations with Iterative Viterbi Decoding Algorithm. 3rd International Symposium on Wireless Communication Systems. Valencia, Spain: IEEE. doi:10.1109/ISWCS.2006.4362391. ISBN 978-1-4244-0397-4.
  • Wang, Qi; Wei, Lei; Kennedy, R.A. (January 2002). "Iterative Viterbi decoding, trellis shaping, and multilevel structure for high-rate parity-concatenated TCM". IEEE Transactions on Communications. 50 (1): 48–55. doi:10.1109/26.975743. ISSN 0090-6778.