複製通道錯誤更正碼的研究

傳統錯誤更正碼所對抗的通道錯誤是替代錯誤，並沒有考慮同步錯誤的情況。如果在一個會發生同步錯誤的通道上使用傳統錯誤更正碼，那麼一旦發生一次同步錯誤，在之後的所有碼字都會因為不對齊而造成錯誤。因此，針對同步錯誤通道設計特別的錯誤更正碼是必要的。最早是由Sellers開始注意到這個問題，他的做法是在每個碼字間插入特別的同步用序列。之後Levenstein發現原先由Varshamov，Tenegolts兩人所發明用來對抗Z通道的VT碼，也可以用來對抗同步錯誤，並進一步地推導出許多同步通道中重要的基本性質。他的做法是每一個固定長度的碼字，可以改固定個數個同步錯誤，後來的多數研究都是類似這種做法。唯一不同的是MacKay，他把低密度同位元檢查碼和一串稱為浮水印碼的序列做互斥運算，用浮水印碼抓回同步，再用低密度同位元檢查碼更正錯誤。除了錯誤更正碼的設計，計算同步錯誤通道的通道容量也是一個一直存在的問題。由於同步錯誤通道並不具有無記憶性的特性，使得分析起來相當困難，除了數值逼近的方法外，直到現在都還只有通道容量的界限。而本篇論文主要針對同步錯誤中的複製錯誤，基於前人把複製通道簡化成複製區塊通道的概念，分析複製區塊通道，進而設計適合的錯誤更正碼，以達到通道容量為目標。並分為零錯誤傳輸方式和允許錯誤傳輸方式兩方面來討論。

關鍵字

複製通道；固定組成碼；單位成本通道容量；非對稱通道；同步錯誤

並列摘要

Insertion and deletion errors are two main classes of synchronization errors. In this thesis, we focus on duplication errors, which is a subclass of insertion errors. Our aim is to find error correcting codes for duplication channels which have a code rate per unit cost higher than 0.5, a rate per unit cost of a simple zero-error coding scheme.

並列關鍵字

Duplication Channels ； Constant Composition Codes ； Capacity per Unit Cost ； Asymmetric Channels ； Synchronization Errors

參考文獻

[4] G.Tenengolts,“Nonbinary codes,correcting single deletion or insertion,” IEEE Transactions on Information Theory, vol. 30, no. 5, pp.766–769,Sep.1984.

[5] Z.Liu and M.Mitzenmacher,“Codes for deletion and insertion channels with segmented errors,” ISIT 2007, pp. 846–850, Jun. 2007.

[6] L.Calabi and W.Hartnett,“A family of codes for the correction of substitution and synchronization errors,” IEEE Transactions on Information Theory, vol. 15, no. 1, pp. 102–106, Jan. 1969.

[7] E.Tanaka and T.Kasai,“Synchronization and substitution error-correcting codes for the levenshtein metric,” IEEE Transactions on Information Theory, vol. 22, no. 2, pp. 156–162, Mar. 1976.

[8] K.A.S.Abdel-Ghaffar,H.C.Ferreira,and L.Cheng,“On linear and cyclic codes for correcting deletions,” ISIT 2007, pp.851–855, Jun.2007.

國際替代計量

複製通道錯誤更正碼的研究

主題瀏覽