Jump to content
    

Как из полинома получить сишный код

Имеется полином, порождающая матрица и кусок кода. 

Часто вижу подобное в помехоустойчивых кодах, но не понимаю как из этой математики получать код.

Для меня тут только понятно как получили данные в массиве.

Почему data проверяют побитно и причем тут операция исключающее или?

Что за результат полинома 471? Еще и в восьмеричной системе судя по всему. Как это учитывается в сишном коде?

unsigned int G[7] = {0x804f, 0x411e, 0x21b7, 0x11e2, 0x09c9, 0x04e5, 0x0273};

unsigned int Encode (unsigned int data)
{
    signed int i = 0;
    unsigned int checkbit = 0;

    for (i = 0; i < 7; i++)      
    {
        if (data & 0x8000)       
        {
            checkbit ^= G[i];      
        }
        data <<= 1;            
    }

    return (checkbit);
}

 

matrix.png

Share this post


Link to post
Share on other sites

х8543+1 = 100111001 = 471 (в восьмеричной) = 0х139

Share this post


Link to post
Share on other sites

х8543+1 = 2^8+2^5+2^4+2^3+2^0 =  100000000+100000+10000+1000+1 = 100111001

 

из двоичной в восьмиричную переводят так: 100111001 = 100_111_001 = 471

 

из двоичной в шестнадцатиричную переводят так: 100111001 = 1_0011_1001 = 139

Share this post


Link to post
Share on other sites

ок, с этим разобрались. А код то как получили?

Share this post


Link to post
Share on other sites

Цитата

Почему data проверяют побитно и причем тут операция исключающее или?

http://kpe.hww.ru/ASM/Book/Charter9/1.htm

на рисунке Рис. 9.4. Схема вычисления CRC-деления.

Там представлена схема деления входного кода на полином чтобы получить остаток, так вот если приглядеться к процессу деления - то видно что его проделывают через "исключающее или"  и посредством сдвига на 1 бит.

Share this post


Link to post
Share on other sites

1 час назад, Lmx2315 сказал:

Там представлена схема деления входного кода на полином чтобы получить остаток, так вот если приглядеться к процессу деления - то видно что его проделывают через "исключающее или"  и посредством сдвига на 1 бит.

Причём это самый медленный способ реализации. Далее идёт табличный который позволяет обрабатывать входящие данные не побитно а байтами и более. Плавный переход тут:

 

https://xakep.ru/2004/03/30/21788/

 

 

Share this post


Link to post
Share on other sites

Классику, классику жанра забыли!!! Ross N. Williams
http://ad-books.narod.ru/asm/articles/crc.pdf
Чуть-чуть не 30 лет уж как...

Share this post


Link to post
Share on other sites

Ключевая фраза в этих статьях - "Полиномиальная арифметика по модулю 2". Кое-что прояснилось.

Но прочитав эти статьи мне все равно бы не удалось написать такой сишный код как в первом посте.

Share this post


Link to post
Share on other sites

10 часов назад, uriy сказал:

мне все равно бы не удалось написать такой сишный код как в первом посте.

Этот код тоже не идеален. Там есть поле для рефакторинга. Если массив G[7] нигде больше не используется, то логично объявить его локально внутри функции с квалификатором static const.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...