Loading article…
符号理論、特に電気通信において、自己同期符号とは、 1つのコードワードの一部、または任意の2つの隣接するコードワードの重複部分によって形成されるシンボルストリームが有効なコードワードではない、一意にデコード可能な符号である。 [1]言い換えれば、アルファベット上の文字列のセット（「コードワード」と呼ばれる）は、2つのコードワードを連結することによって得られる各文字列について、2番目のシンボルで始まり最後から2番目のシンボルで終わる部分文字列に部分文字列としてコードワードが含まれていない場合、自己同期符号と呼ばれる。すべての自己同期符号はプレフィックス符号であるが、すべてのプレフィックス符号が自己同期であるわけではない。
自己同期コードの他の用語は、同期コード[2]または、あいまいにコンマフリーコード[3]です。自己同期コードでは、シンボルストリームに未訂正エラーが発生しない限り、送信されたコードワードを適切にフレーミングできます。外部同期は必要ありません。自己同期コードでは、ストリーム内の未訂正エラーからの回復も可能になります。ほとんどのプレフィックスコードでは、1ビットの未訂正エラーがストリーム内でさらにエラーを伝播させ、後続のデータを破損させる可能性があります。
自己同期コードの重要性は、データ伝送だけに限りません。自己同期は、デジタルでエンコードされたテキストなどのデータ回復にも役立ちます。
例
- UTF-8 は、マルチバイト コード ポイントの先頭バイト (
11xxxxxx) と後続のバイト ( ) のビット パターンが異なるため、自己同期化します。10xxxxxx - 高レベルデータリンク制御(HDLC)
- 高度データ通信制御手順(ADCCP)
- フィボナッチコーディング
反例:
- プレフィックス コード {00, 11} は自己同期しません。0、1、01、10 はコードではありませんが、00 と 11 はコードです。
- ababにba が含まれているため、プレフィックス コード { ab , ba } は自己同期しません。
- プレフィックスコードb ∗ a (クリーネスターを使用) は、コードワードbaにコードワードaが含まれているため、自己同期しません (新しいコードワードがa の後に始まる場合でも) 。
参照
参考文献
- ^ 「自己同期コード - 用語集」。
- ^ Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010).コードとオートマトン. 数学とその応用百科事典。第129巻。ケンブリッジ、イギリス：ケンブリッジ大学出版局。p. 137。ISBN 978-0-521-88831-8.ZBL1187.94001 。
- ^ Berstel, Jean; Perrin, Dominique (1985).コードの理論. 純粋および応用数学. 第117巻.アカデミックプレス. p. 377. Zbl 0587.68066.
さらに読む
- 「自己同期コード」。連邦規格 1037C: 電気通信: 電気通信用語集。一般調達局。1996 年 8 月 6 日。2022 年 1 月 22 日にオリジナルからアーカイブされました。
- ミリタリースタンダード188