(COBS) – algorytm kodowania ciągu liczb (zwykle bajtów) w postaci ciągu, w którym nie występuje jeden wyróżniony symbol (zwykle zero). Jego pomysłodawcą i autorem jest . Podstawową zaletą algorytmu jest znikomy narzut zwiększający rozmiar zakodowanych danych. Głównym zastosowaniem algorytmu jest wspomaganie pakietyzacji strumienia danych w transmisji szeregowej.

Historia Prezentacja algorytmu miała miejsce na konferencji SIGCOMM poświęconej zagadnieniom komunikacyjnym jak również został on zgłoszony jako propozycja do wykorzystania w protokole PPP. Algorytm kodowania był tematem pracy doktorskiej, którą przedłożył na Uniwersytecie Stanforda w 1998. Rok później artykuł z opisem algorytmu został opublikowany czasopiśmie organizacji IEEE. W 2020 zaadaptowano wykorzystanie algorytmu dla półbajtów. W 2022 roku zauważono, że w sprzyjających okolicznościach działanie algorytmu można przeprowadzić równolegle na fragmentach danych co znacznie skraca czas przetwarzania zwłaszcza w realizacji sprzętowej.

Motywacja W transmisji danych z wykorzystaniem łącza szeregowego w warstwie fizycznej warstwa łącza danych tworzy ramki, które kapsułkują dane z wyższej warstwy. Każda ramka zawiera znaczniki, które jednoznacznie pozwalają określić jej początek i koniec. W systemach opartych na transmisji danych w postaci ciągów tekstowych znacznik startu to jeden ze znaków, który nie jest używany w kodowaniu danych. W przypadku, gdy łącze danych ma przesyłać dowolne dane binarne, może się zdarzyć, że wśród nich pojawią się takie, które będą przyjmowały wartości tożsame z używanymi do rozpoznawania początku i końca ramki. Aby uniknąć takich kolizji stosowane są metody pozwalające na ich eliminację ze strumienia danych. Za przykład można wskazać SLIP lub PPP. Polegają one głównie na podmianie każdego bajtu mającego specjalne znaczenie przez odpowiednie zastąpienie sekwencją dwóch bajtów. Jeśli nastąpi próba wysłania danych składających się z samych „zarezerwowanych” wartości, to w takim przypadku długość danych do przesłania w warstwie fizycznej ulegnie podwojeniu.

W proponowanym algorytmie narzut związany z eliminacją wartości zarezerwowanych nie przekracza 1 bajta na każde 254 bajty danych.

Opis W wersji podstawowej algorytm skupia się na sposobie zapisu ciągu liczb z pełnego zakresu liczb ośmiobitowych od 0 do 255 na odpowiadający mu ciąg liczb z zakresu od 1 do 255. Jeśli zachodzi konieczność eliminacji wartości innej niż zero, to można wszystkie bajty wyniku zamienić wykonując na nich funkcję XOR z wartością do usunięcia.

Kody Do reprezentacji wartości oryginalnego ciągu COBS używa następujących kodów:

Kod (hex) Znaczenie Opis 01 00 bajt o wartości zero 02 XX XX 00 dowolny niezerowy bajt danych + bajt o wartości zero 03 XX XX XX XX 00 dowolne dwa niezerowe bajty danych + bajt o wartości zero nn XX … XX XX … XX 00 (nn-1) niezerowych bajtów danych + bajt o wartości zero FE XX … XX XX … XX 00 253 niezerowe bajty danych + bajt o wartości zero FF XX … XX XX … XX 254 niezerowe bajty danych, po których nie ma bajtu o wartości zero

W powyższym zestawieniu kodów nie istnieje wartość 00, która jest niedozwolona.

Kodowanie Ciąg wejściowy o dowolnej długości dzielony jest na fragmenty nie dłuższe niż 254 bajty, w których bajt o wartości zero występuje dokładnie na końcu. Jest on zastępowany w ciągu wyjściowym odpowiadającym mu kodem z domyślnym zerem. Jeśli taki podciąg nie istnieje to w jego miejsce jest wstawiany wyjątek zaczynający się kodem 255, który pozwala na kodowanie długich bezzerowych ciągów danych. Wyjątek stanowi również ostatni fragment nie dłuższy niż 253 bajty, który domyślnie zakłada istnienie wirtualnego zera tuż za ostatnim bajtem pakietu. Po zakodowaniu w wyjściowym strumieniu danych nie ma wartości zero, które można jednoznacznie wykorzystać do wskazania granic między pakietami.

Przykłady Pusta kratka na końcu to wirtualne zero. Pogrubiona czcionka oznacza pierwszy bajt kodu. Wielokropek to ciąg niezerowych wartości.

+ Oryginalny przykład ze specyfikacji dane 45 00 00 2C 4C 79 00 00 40 06 4F 37 kod 02 45 01 04 2C 4C 79 01 05 40 06 4F 37

+ Ciąg z sekwencją niezerowych bajtów od pozycji 9 do 264 pozycja 1 2 3 4 5 6 7 8 … 263 264 265 266 dane 44 69 6C 65 00 00 74 00 … 54 61 — kod 05 44 69 6C 65 01 02 74 FF … 03 54 61

+ Ciąg z sekwencją 254 niezerowych bajtów na końcu pozycja 1 2 3 4 5 6 7 … 258 259 260 dane F0 9F 8D 86 00 F0 9F … 92 A6 — kod 05 F0 9F 8D 86 FF F0 9F … 92 A6

+ Pusty pakiet dane kod 01

+ Bajt zero dane 00 kod 01 01

Własności Bardzo mały narzut na rozmiar danych po kodowaniu. Bardzo prosta synchronizacja. Kodowanie wymaga bufora o rozmiarze 254 bajtów Trywialna implementacja w każdym języku programowania

Obserwacje Strumień danych zakodowanych algorytmem COBS dzielony jest na pakiety w miejscu napotkania wartości specjalnej . Zachowanie na okoliczność występowania sekwencji zer w takim ciągu nie jest zdefiniowane. Jednym z rozwiązań jest przyjęcie, że oznacza ona brak pakietu. Ciąg zerowych bajtów może być więc wykorzystany jako wypełnienie jeżeli brakuje danych do transmisji. Protokół MS/TP, używany jako warstwa łącza danych w transmisji po RS-485 w protokole BACnet, stosuje algorytm COBS do eliminacji wartości specjalnej z bloku danych i sumy kontrolnej. Sekwencja bajtów oznacza w nim początek nowej ramki. Algorytm COBS może być dobrym wyborem w przypadku implementacji pakietyzacji przy połączeniach z wykorzystaniem protokołu TCP. Algorytm nie jest powszechnie stosowany w praktyce. Jednym z powodów może być brak oficjalnego wsparcia w ramach standardu PPP. Algorytm operuje na buforach danych, wobec czego nie może być stosowany w przypadku gdy oczekiwane jest natychmiastowe generowanie danych wyjściowych w przetwarzaniu potokowym. W przypadku obsługi pakietów o niewielkich rozmiarach, stały jednobajtowy narzut może być odbierany jako znaczny. Dla pakietów jednobajtowych narzut stanowi 100%, a dla czterobajtowych 25% oryginalnej wiadomości.

Uwagi

Przypisy

Linki zewnętrzne

Kategoria:Kody