December 7th, 2011

Водолазик

И также о полиномах

       Стандартная ячейка ATM состоит из 48 байтов данных и 5 байтов заголовка. Последний байт — HEC (Header Checksum), циклическая контрольная сумма, или CRC с полиномом 8,2,1,0. В начале регистр для вычисления CRC обнуляется, а после вычисления результат складывается по модулю 2 с константой 010101012 (см.).

  0   1   2   3   4   5         52   байты
+---+---+---+---+---+---+-...-+---+
|   Заголовок   |HEC|    Данные   |
+---+---+---+---+---+---+-...-+---+

       У ячеек ATM нет синхрослова. Для выделения заголовка ATM во входном потоке данных для каждых пяти байтов производится сложение с константой 010101012 пятого байта, вычисление CRC для всех пяти байтов и сравнение результата с нулём. Нуль говорит, что контрольная сумма сошлась, и синхронизация считается найденной.
       Существует формат укороченных ячеек ATM длиной 400 битов (50 байтов). На 48 байтов данных приходится 2 байта заголовка. Был записан битовый поток, содержащий три типа заголовков ячеек:

1) 1111 1111 0001 1011
2) 1111 1111 0011 1110
3) 0000 0000 0000 1010

       Никакой синхрокомбинации не видно. Значит, для синхронизации по заголовку авторы формата-коротышки должны были использовать механизм, аналогичный HEC во «взрослом» ATM.
       По виду заголовка № 3 следует, что при вычислении контрольной суммы над нулевыми входными данными результат отличен от нуля.
       Возможно, регистр был инициализирован ненулевым значением. Также возможен вариант, когда результат вычисления был сложен по модулю 2 с некоторой маской. Маска в данном случае 10102. Этот вариант выглядит более правдоподобно, на нём мы и остановимся.
       После вычитания маски получаем:

1) 1111 1111 0001 0001
2) 1111 1111 0011 0100

       Для определения порождающего полинома CRC вспомним теорию. CRC, будучи циклическим кодом, формируется как остаток r(x) от деления полинома xn×m(x) на порождающий полином g(x), где m(x) — полином исходного сообщения, g(x) — порождающий полином циклического кода, n — степень порождающего полинома g(x).
       Сумма xn×m(x)+r(x) будет делиться на g(x) без остатка.
       Заголовки № 1 и № 2 представляют собой полиномы, делящиеся без остатка на искомый полином g(x). Воспользуемся алгоритмом Евклида для нахождения НОД (№ 1, № 2).
       Хозяйке на заметку: арифметические действия с полиномами с коэффициентами в GF(2) — увлекательная и весёлая забава.
       Полином представляется в виде списка степеней, при сложении (либо вычитании — это одна и та же операция) одинаковые степени вычёркиваются.
       Степени нумеруются от 0 (единица) до n (xn). Б́oльшим из двух считается полином с большей степенью.
       Итак:

    15,14,13,12,11,10,9,8,4,0      |_ 15,14,13,12,11,10,9,8,5,4,2
    15,14,13,12,11,10,9,8,5,4,2       0
    _____
    5,2,0
    ~~~~~

    15,14,13,12,11,10,9,8,4,0      |_ 5,2,0
    15,12,10                          10,9,8,5,2,0
    ________________
    14,13,11,9,8,4,0
    14,11,9
    ________
    13,8,4,0
    13,10,8
    ______
    10,4,0
    10,7,5
    _______
    7,5,4,0
    7,4,2
    _____
    5,2,0
    5,2,0   
    -        разделили без остатка
    ~~~~~

       Итак, НОД — полином 5,2,0.
       Окончательно получаем параметры CRC для укороченного ATM:
— порождающий полином x5+x2+1;
— начальное заполнение регистра — нули;
— после вычисления CRC складывается по модулю 2 с константой 010102 для получения HEC.
       Из оставшихся битов первые восемь, скорее всего, являются VCI (идентификатором виртуального канала), а оставшиеся три — PTI (payload type identifier).

пруфлинк




========================
       * и немедленно выпил
феолософ

Зима

Зима осторожно подкралась и белой порошею
По просекам бродит, последней листвою звеня.
Я знаю, что где-то горит моё ясное солнышко,
Но светит, но светит оно уже не для меня.
       Вот и ушло тепло  на юг...
       Много ли нам его досталось?..
       Было тепло – и вдруг
       Стало бело вокруг.
       Что же теперь, мой друг, осталось?

Пирог на сочельник и слёзы свечей оплывающих,
И саночек лёгких весёлый рождественский скрип,
И след от полозьев, в морозную синь убегающий,
И птицы, отставшей от стаи, пронзительный крик.

И я, как та птица, гляжу на леса серебрёные
И первую наледь ломаю, взлетев тяжело,
И крылья метели, и крылья метели калёные
Своим рассекаю пока ещё тёплым крылом.
       Вот и ушло тепло  на юг...
       Много ли нам его досталось?..
       Было тепло – и вдруг
       Стало бело вокруг.
       Что же теперь, мой друг, осталось?

Остыну, промёрзну, как речка, до самого донышка
И не ворочусь уж из снежного из далека...
А где-то по небу плывёт и плывёт моё солнышко,
Да вот закрывают его от меня облака.
Я знаю, что где-то плывет моё ясное солнышко,
Да вот закрывают его от меня облака...

© Валерий Боков