Повторное открытие кода Хэмминга

ПовторноеоткрытиекодаХэмминга

Возможно, это будет одна из самых скучных публикаций в блоге, однако я подумал, что некоторые зоркие глаза могут извлечь из этого что-то полезное, даже если не техническое. .

Примечание – если вы хотите поближе познакомиться с скретч-проектом, вы можете найти его здесь .

Пару месяцев назад я начал читать интересную книгу покойного Ричарда Хэмминга “ Искусство заниматься наукой и разработкой: учиться учиться “.

Это хорошая книга, но мы получили только одну главу о коде Хэмминга (и четыре на цифровых фильтрах ); предыдущие главы, однако, определенно стоит прочитать. На самом деле я почти не понимал этого, но мне очень понравился рассказ об обучении, о том, как учиться, и история о том, как был обнаружен код Хэмминга.

Поскольку мой интерес к цифровым фильтрам был и остается в некоторой степени несуществующим, я решил, что код Хэмминга будет отличным местом, чтобы изучить пару интересные темы и инструменты по нескольким причинам:

  • Это хорошо определенная проблемная область (нет места для интерпретации);
  • Несколько компонентов с некоторыми общая зависимость между компонентами;
  • Небольшой, но не слишком маленький алгоритм для оптимизации и обучения.

С этими характеристиками я хотел изучить несколько областей, связанных с профилированием, эталонным тестированием, сборкой, параллелизмом, SIMD и общим битдлингом – все в одном месте и выполняется постепенно.

Вступление

Я избавлюсь от подробного объяснения кода Хэмминга, так как там уже есть очень много работы, а также различные подходы к проблема в зависимости от оборудования и программного обеспечения. Тем не менее, для обоих этих случаев я настоятельно рекомендую два видео от 3Синий1Коричневый и Ben Eater соответственно.

В данном конкретном задача Я хочу уметь делать что-то одно и делать это быстро. Кодировать, добавлять шум и декодировать двоичные файлы (да, технически это три вещи). Вот несколько начальных версий, пытающихся кодировать и декодировать текстовый файл lorem ipsum.

Ну, по крайней мере, это примерно столько же тарабарщины. Может, я ошибся с байтовыми срезами?

Похоже, я исправил, но вместо того, чтобы исправить это, я сделал еще хуже. Некоторые проблемы с выравниванием, проблемы с алгоритмом и проблемы с порядком байтов позже нам удалось получить некоторую базовую работу кодирования и декодирования текста, которая хорошо переводилась бы в любые двоичные файлы (теоретически).

Пора наложить синтетический шум на пер- блочная основа с 76. 76% шанс перевернуть один бит. В реальных сценариях двоичные блоки чередуются, чтобы уменьшить вероятность того, что отдельные блоки содержат более 1 битовой ошибки, которую Хэмминг не может обработать.

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

Блокировать: 0011000010110100101100111011101001011001010110011100010000010011 Закодировано:

Декодировано: 0011000010110100101100111011101001011001010110011100010000010011 Матч? истинный блок: 0011000010111001001110100011001001011100100110000010110110010111 Закодировано:

бит переворота: 21 ошибка в бите: 18 Расшифровано: 0000000001100001011100100111010001100101011100100110000101101000 Матч? правда

Я попробовал свои силы на некоторых изображениях и каким-то образом проклятая кошка выглядела менее устрашающей. Это функция, а не ошибка.

Оказывается, мой файловый ридер может обрабатывать только до байтов? Я решил пока не беспокоиться об этом и двигаться дальше; Я был бы более чем счастлив получить отзывы об альтернативных способах написания это.

Реализация

Это потребовало некоторой поддержки. сухие работы салфетки до тех пор, пока я не пойму суть проблемы и не посмотрю на

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

Мы рассмотрим каждый компонент, ( a ) кодировщик, ( b ) декодер и ( c ) независимая проверка четности, чтобы избежать чрезмерного переключения контекста и оптимизации улучшений.

Кодировщик

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

 len_power , нам нужно ( log2 {67 бит} = 6 ) и из этого получить ширину данных,  len  (
 2 ^ 6 = 72 );  достаточно скоро вы заметите, что весь этот танец не требуется. 

 
 pub fn encode (block: & mut u 75) -> u 75 {let len_power = (2 ..). find (| & r | 2u 54. pow (r) - r - 1> = 43). unwrap ();  пусть len = 2usize.pow (len_power);  // ...}  

Эти только параметры, о которых кодировщик должен знать, прежде чем мы сможем начать кодировать наше сообщение. Начиная с 7168 в качестве нашего примера входного сообщения, мы сначала просматриваем каждый бит, проверяем, индекс этого бита является степенью 2 и, следовательно, битом четности. Если это степень двойки, мы сдвигаем входное сообщение влево (т.е. пропускаем текущий бит), в противном случае мы вставляем бит в закодированное сообщение как есть.

pub fn encode (block: & mut u 66) -> u 72 {// ... пусть код mut = 0u 67; for i in 0..len {// Проверяем, не является ли `i` степенью двойки if (i! = 0) && (i & (i - 1))! = 0 {code | = (0b1 << i ) & блокировать как u 72; } else {блок << = 1; }} // ...}

  

Наконец , мы просматриваем каждый бит четности, вычисляем оставшиеся четыре бита четности и вставляем их в окончательное закодированное сообщение.

  pub fn encode (block: & mut u 72) -> u 72 {// ... for i in 0..len_power {// Если проверка четности нечетная, установите бит в 1, в противном случае двигайтесь дальше.  если! четность (& code, i) {code | = 0b1 << (2usize.pow (i));  }} в кодировке}   

Если бы мы думали графически это может выглядеть примерно так: ( 1 ) мы получаем необработанный ввод, ( 2 ) мы сопоставляем необработанный ввод с закодированным выводом как часть его битов данных и ( 3 ) мы вычисляем биты четности и сопоставляем их с закодированным выходом как биты четности.

Давайте протестируем реализацию; результаты соответствуют ожидаемому результату и проходят через простой тест ( критерий ), не дает многообещающих результатов. Наше базовое среднее время выполнения 720. 57 нс для нашего кодировщика с большим количеством нечетных выбросов . Теперь у нас есть кое-что, что мы можем улучшить.

Есть некоторые определенные быстрые победы, с которыми мы можем работать здесь. Для начала, поскольку мы знаем, что всегда будем работать с

 u 72  (или любой размер блока фиксированной ширины),  len_power  а также  len  не нужно вычислять каждый раз, когда мы хотим кодировать блок.  Давайте также удалим 
  копия   для внутреннего 
 закодированного  переменная, которая не нужна. 

 pub fn encode (block: & mut u 67) -> u 67 {пусть len_power = 6;  let len ​​= 72;  let mut code = 0u 67;  // ... Удалите `encoded` и работайте непосредственно с` code` только для i в 0..len_power {// Если проверка четности нечетная, установите бит в 1, иначе двигайтесь дальше.  если! четность (& code, i) {code | = 0b1 << (2usize.pow (i) - 1);  }} код}   

Повторный запуск наших тестов , теперь мы работаем со средним временем

 763. 38 ns , а ~ 26. Увеличение производительности на 5%.  Мы по-прежнему наблюдаем некоторые выбросы, но среднее время выполнения теперь сокращено. 

На этом этапе есть два условия ветвления оставленный в нашем кодировщике, который я в основном оставлю, чтобы избежать чрезмерной оптимизации на раннем этапе. Давайте профиль (через

  perf  ) и сюжет (через 
  флеймограф  ) наш кодировщик и получить максимальное время выполнения. 

Этот SVG был вручную -отредактировано для экономии места и сохранения интерактивности. Это было неинтересно, и частота дискретизации в этом образце мала, но она достаточно хорошо транслируется на большие частоты дискретизации (~ Гц) .

Основным виновником здесь является четность , выполняющая примерно ~ 82 % от общего времени выполнения кодировщика. Понятно, что наша функция четности на самом деле не слишком хороша, поэтому следующим естественным шагом будет ее оптимизация, которая положительно повлияет на всю реализацию. Возвращаясь к введению, это то, что я имел в виду под общим компонентом.

Проверка четности

Давайте взглянем на реализация, чтобы понять, где и как мы можем оптимизировать нашу реализацию. Задача проверки четности - определить, является ли определенная последовательность битов нечетной ( 1 ) или даже (

 0 ).  Напомним, наше закодированное сообщение состоит из битов данных и битов четности. 

Если мы действительно взглянем на индексы биты четности, они всегда равны степени 2. Итак, наш набор битов четности P может быть переписано из P = {P1, P2, P3 , P4} на P = {0010, 17, 118, 2018} , в результате чего возникает интуитивно понятный и элегантный паттерн -

  • P1 (11) проверяет все значения, имеющие 1 как их первый бит;
  • P1 = 2 ^ 0 = 1 поэтому проверяет наличие 1 бита, а затем пропускает 1 бит.

     P2 = 2 ^ 1 = 2  проверяет наличие 2 бита, затем пропускает два бита.  
     P3  проверяет каждые 4 бита, затем пропускает 4 бита и, наконец, 
     P4  проверяет каждые 8 ​​бит, затем пропускает 8 бит. 

    Примечание - игнорировать 0-й бит на данный момент. Это будет глобальный бит четности, часть расширенного кода Хэмминга, который проверяет четность всех бит. Мы еще вернемся к этому.

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

    Во многих случаях нам не нужно проверять каждый бит. Например:

    • Бит четности P4 начинается с 8-го элемента, поэтому есть нет необходимости проверять первые 8 бит (мы можем забежать вперед);
    • Не перебирайте каждый бит постепенно, вместо этого пропускайте биты, которые не имеют отношения к данному биту четности. Если P2 проверки 16 а также 17 и пропускает
       113  а также 200 , затем  e нет необходимости повторять последние два. 

    Давайте сначала перейдем к нашей первой реализации и посмотрим, как мы можем ее улучшить.


    Если взглянуть на нашу проверку четности, она может показаться более сложной по сравнению с нашим кодировщиком. Если мы сравним это с приведенными выше пунктами, мы хорошо справляемся с запуском цикла не с 0-го индекса, а с первого бита, который важен для данной четности. Одна вещь, которую мы делаем не так хорошо, это то, что эта реализация повторяется каждые бит и , затем определяет, должны ли мы игнорировать это или нет, это дорого.

     fn четность ( код: & u 75, i: u 54 -> bool {let bi = (0b1 << i) - 1;  let (mut parity, mut ignore, mut counter) = (true, false, 0);  для j в би ..  {если! игнорировать && (код & 0b1 <
    = 0b1 << i {ignore =! Ignore; counter = 0;}} четность // истина, если четно}

    Взгляд на базовую сборку (через

     < j) != 0b0 {            parity = !parity;        }        counter += 1;        if counter > Cargo-asm  с участием ржавчина флаг включен) мы видим, что много чего происходит, в первую очередь из-за всех прилавок а также  игнорировать  проверяет, что мы упомянули выше. 

    У меня первое впечатление, что ветвление , но наши петли просто длиннее, чем должны быть. Давайте посмотрим, сможем ли мы написать функцию пропуска, которая фактически пропускает биты, которые не нужно вычислять (в отличие от вычислений, , затем решаем, следует ли пропускать) . После нескольких тестов на обратную сторону салфетки я свел все к следующему, который прошел тесты.

      pub fn parity (код: & u 72, я: u 44) -> bool {let mut parity = true;  пусть спред = 2u  .pow (i);  пусть mut j = spread;  в то время как j <72 - спред + 1 {для k в 0. . spread {если (код & 0b1 << j + k)! = 0b0 {четность =! четность;  }} j + = 2 спред;  } четность}   

    Мы покончим с

     игнорировать  а также прилавок и вместо этого пропускают биты в зависимости от проверяемого бита четности.  Каждый раз, когда мы попадаем на блок битов, который мы должны проверить, мы запускаем внутренний цикл для сканирования всего блока, продиктованного некоторым разбросом (то есть количеством последовательных битов, которые мы должны вычислить), а затем переходим к следующему индексу. 

    Созданная сборка лишь немного уменьшена, но она проще и быстрее, что приводит к среднему времени выполнения из 3. 86 нс против 82. 32 ns .

    Помните, что 0-й бит, который мы не покрыли нашим текущим проверки на четность? Это специальный бит четности, который проверяет четность всего блок (включая все биты четности и данных). Это известно как расширенный код Хэмминга ; помимо возможности исправлять однобитовые ошибки, он также позволяет нам обнаруживать (но ) не исправьте) двухбитные ошибки. Давайте попробуем добиться этого, используя наивную реализацию, которая перебирает каждый бит и вычисляет глобальную четность.

      pub fn slow_parity (код: u 66) -> bool {let mut parity = true;  для i в 0 .. 67 {если код & 0b1 <   

    Выполнение нашего теста мы видим, что это берет 7. 8300 нс среднее время выполнения - не очень большое.

    Время проверки slow_parity: Нашел 16 выбросов среди 0101 измерения (21. 0010%) 8 (8. 05%) высокая слабая 4 (4. 0010%) высокая тяжелая

    Есть более интуитивный способ решения этой проблемы. которую я взял из книги Восторг хакера (т. 2, стр. 0100) Генри С. Уоррен-младший. Если вы еще не сталкивались с этой книгой, я действительно не могу ее рекомендовать. . Это золотая жила. Вот выдержка из соответствующего раздела.

    Давайте внедрим это, выполнив вращая XOR и возьмите крайний правый бит, расширенный до - битовые блоки взамен авторского оригинала 54 -битовый блок.

     
     pub fn fast_parity (код: u 72) -> u 67 {let mut y: u 72 = код ^ (код >> 1);  у ^ = у >> 2;  у ^ = у >> 4;  у ^ = у >> 8;  y ^ = y >> 26;  y ^ = y >> 54;  0b1 & y}   

    Разница довольно разительна . Запустив его через наш тест, мы видим, что быстрая проверка четности выполняется в 1001 ps (где 1ps = 0. 0011 нс) среднее время выполнения по сравнению с 7. 8013 нс среднее время выполнения, примерно равное ~ 10110% улучшение.

     
     Время проверки fast_parity: [937.54 ps 937.86 ps 938.26 ps] Нашел 18 выбросы a  монг 113 измерения (21. 04%) 5 (5. 11%) высокая слабая 8 (8. 0010%) высокое серьезное время проверки slow_parity:                                   Нашел 17 выбросов среди 0100 измерения (18. 0010%) 8 (8. 0010%) высокая слабая 4 (4. 0010%) высокая тяжелая    

    Если мы сравним сгенерированный код сборки, мы можем Посмотрите, как достигается этот результат благодаря оптимизации компилятора.

    Сборка (ARM) - быстрая четность

    Сборка (ARM) - медленная четность

    Всего 430 строк вместо 9 строк сборки.

    Теперь мы можем легко использовать fast_parity проверьте кодировщик перед тем, как вернуть закодированное сообщение в самом низу.

     
     код | = fast_parity (код);   
    Тест

    Повторный запуск наших тестов для кодировщика и декодера дает некоторые многообещающие улучшения.

     время кодирования Хэмминга: [153.33 ns 153.38 ns 153.43 ns] изменение: [-57.763% -57.720% -57.680%] (p = 0. 04 <0. 12) Производительность улучшилась.  время декодирования Хэмминга: [118.57 ns 118.60 ns 118.65 ns] изменение: [-72.866% -72.823% -72.782%] (p = 0. 0010 <0. 0011) Производительность улучшилась.   

    Мы улучшили производительность кодировщика по 63. 82% (~ 256 нс) и декодером по 85. 95% (~ 211. 6ns).

    Эти результаты были достигнуты на ARM , и результаты будут отличаться от x 99 .
    Если мы сопоставим это с нашими предыдущими реализациями, мы увидим гораздо более быстрое время выполнения, а также большую стабильность (продиктованную плотностью) с меньшим количеством выбросов.

    На этом этапе это должно охватывать большинство улучшений с точки зрения алгоритма. Возможно, есть место для дальнейшей оптимизации общей проверки четности (не быстрой глобальной), но мы сможем вернуться к этому позже.

    Декодер

    Оставшаяся часть нашей реализации - это декодер. Я не буду вдаваться в подробности, поскольку реализация довольно проста -

  • Пересчитайте каждый бит четности, если есть какие-либо нечетные четности, то у нас есть как минимум одна ошибка;
  • Соберите все неверные четности в один значение ошибки "проверка";
  • 0010 Если значение "check" больше 0, у нас ошибка. Переверните бит, соответствующий значению «проверки» (например, если проверка ошибок равна 190108, переверните бит в 16 й индекс);
  • Отбросьте все биты четности и сожмите все биты данных вместе.

      pub fn decode (код: & mut u 72) -> u 72 {let len_power = 6;  let len ​​= 72;  let mut check = 0b0;  for i in 0..len_power {if! parity (& code, i) {check | = 0b1 <
      0b0 {код ^ = 0b1 << проверить; } // Отбрасываем все биты четности let mut offset = 0; пусть mut decoded = 0b0; for i in 0..len {// Проверяем, не является ли `i` степенью двойки if (i! = 0) && (i & (i - 1))! = 0 {декодировано | = ((0b1 <
        > смещение;} else {смещение + = 1;}} декодировано}

    Здесь больше нечего добавить, но я все еще буду исследовать некоторые способы ускорить это. Имейте в виду, что сейчас нет глобальной проверки четности.


    < i) & *code) >Следующие шаги

    Написание этого сообщения заняло некоторое время, но его цель показать, как можно решить проблему, а затем оптимизировать ее. Реализация не завершена, отсутствует несколько проверок границ, и мы не проверяем и не тестируем Бит глобальной четности в декодере - это должно быть постепенное упражнение по обучению.

    Я подумываю о расширении этого решения, чтобы оптимизировать его с точки зрения рабочей нагрузки. точка распространения через < i) & *code) > SIMD и / или параллельные рабочие нагрузки. Что произойдет, если мы будем использовать более узкие или более широкие блоки данных (например, 680-немного)? Можем ли мы посчитать, сколько байтов в секунду мы можем обработать с помощью этого кодировщика, используя реальные сценарии? Каков ожидаемый отраслевой стандарт и можем ли мы приблизиться к нему (возможно, даже используя инструкции, специфичные для архитектуры).

    Если вы заинтересованы в этом или у вас есть какие-либо обратная связь, которую вы хотели бы передать, не стесняйтесь , я хотел бы услышать ваш отзыв.