Samosynchronizujący się kod

Nie mylić z sygnałem samotaktującym .

W teorii kodowania , zwłaszcza w telekomunikacji , kod samosynchronizujący się jest jednoznacznie dekodowalnym kodem , w którym strumień symboli utworzony przez część jednego słowa kodowego lub przez nałożoną część dowolnych dwóch sąsiednich słów kodowych nie jest prawidłowym słowem kodowym . Innymi słowy, zestaw ciągów (zwanych „słowami kodowymi”) nad alfabetem nazywany jest kodem samosynchronizującym się, jeśli dla każdego ciągu otrzymanego przez połączenie dwóch słów kodowych podłańcuch zaczyna się od drugiego symbolu i kończy na przedostatnim symbol nie zawiera żadnego słowa kodowego jako podłańcucha. Każdy samosynchronizujący się kod to a kod prefiksu , ale nie wszystkie kody prefiksu są samosynchronizujące się.

Inne terminy dotyczące kodu samosynchronizującego się to kod zsynchronizowany lub, niejednoznacznie, kod bez przecinków . Kod samosynchronizujący się umożliwia prawidłowe ramkowanie przesyłanych słów kodowych pod warunkiem, że w strumieniu symboli nie występują nieskorygowane błędy ; zewnętrzna synchronizacja nie jest wymagana. Kody samosynchronizujące umożliwiają również odzyskiwanie po nieskorygowanych błędach w strumieniu; w przypadku większości kodów prefiksów nieskorygowany błąd w pojedynczym bicie może propagować błędy dalej w strumieniu i powodować uszkodzenie kolejnych danych .

Znaczenie kodów samosynchronizujących się nie ogranicza się do transmisji danych . Samosynchronizacja ułatwia również niektóre przypadki odzyskiwania danych , na przykład tekstu zakodowanego cyfrowo .

Przykłady

• Kod prefiksu {00, 11} jest samosynchronizujący się, ponieważ 0, 1, 01 i 10 nie są kodami.
• UTF-8 jest samosynchronizujący się, ponieważ jego wiodące ( 11xxxxxx ) i końcowe ( 10xxxxxx ) bajty mają różne wzorce bitowe.
• Kontrola łącza danych wysokiego poziomu (HDLC)
• Zaawansowane procedury kontroli transmisji danych (ADCCP)
• Kodowanie Fibonacciego

kontrprzykłady:

• Kod prefiksu { ab , ba } nie jest samosynchronizujący się, ponieważ abab zawiera ba .
• Kod przedrostka b ^∗ a (przy użyciu Kleene star ) nie jest samosynchronizujący się (nawet jeśli każde nowe słowo kodowe po prostu zaczyna się po a ), ponieważ słowo kodowe ba zawiera słowo kodowe a .

Zobacz też

• Poślizg bitu
• Kod przecinka
• Sygnał samotaktujący
• Konsekwentne upychanie bajtów narzutowych

•   Berstel, Jean; Perrin, Dominique (1985), Theory of Codes , Pure and Applied Mathematics, tom. 117, Prasa Akademicka, Zbl 0587.68066
•    Berstel, Jean; Perrin, Dominik; Reutenauer, Christophe (2010). Kody i automaty . Encyklopedia matematyki i jej zastosowań . Tom. 129. Cambridge: Cambridge University Press . ISBN 978-0-521-88831-8 . Zbl 1187.94001 .
• Ten artykuł zawiera materiały należące do domeny publicznej z normy federalnej 1037C . Administracja usług ogólnych . (w celu wsparcia MIL-STD-188 ).