Category: техника

Category was added automatically. Read all entries about "техника".

wall

Верхний пост

Всем привет.

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

Я не пишу под замок. Сейчас "под глазиком" лежит n штук недописанных постов, под замком один пост с оффлайновыми контактами. И может быть ещё что-то случайное из давней древности.

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

Код Хэмминга

Есть 10 типов людей: те, кто понимают двоичную систему счисления и те, кто нет.


Я несколько раз про него читал и вроде бы даже один раз делал. Но каждый раз это было как-то непросто. То есть воспринималось как некоторая (хотя и не слишком сложная) магия, которую надо в правильном порядке сделать и тогда -- крэкс-пэкс-фэкс -- получаем в синдроме номер ошибочного бита. Откуда он там? Ну как же, мы же вместе вычисляли, по формулам. Вот формулы, вот матрица преобразования -- там всё получается, можете проверить. Доктор, а откуда у вас такие формулы? А их придумал великий Хэмминг.

Richard Wesley Hamming, кстати, если и не великий, то выдающийся без дураков. Мало того, что он сам получил премию Тьюринга и проч., так ещё и имени его учреждена медаль. Вручается с 1988 за достижения в теории информации.

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

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

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

Это правда просто, совсем просто, и даже формул почти не будет. Но вот двоичная система счисления понадобится, не без этого.

Collapse )
Collapse )

Тут можно пять минут подумать.

[Код Хэмминга: решение]Код Хэмминга: решение
Постановка, высказанная в такой форме оставляет на самом деле очень мало свободы для решения. Если заранее знать, что решение есть, то нужно просто идти вперед по единственному очевидному пути.

Давайте посмотрим на пример:

c0c11c2001c30110100

приемник это получил и вычислил свои контрольные биты

c'0c'1c'2c'3

Теперь, если в синдроме должен быть номер ошибочного бита, а сравнение c3 и c'3 отвечает за третий (считаем от 0) бит синдрома, то это сравнение должно сообщать о наличие/отсутствие ошибки в битах с номерами 8, 9, 10, .. 15. Просто потому, что если значение синдрома от 8 до 15, то в двоичной системе это от 10002 до 11112 и его третий (старший в данном случае) бит установлен в 1. Отсюда получаем:

c3 = d9 + d10 + d11 + d12 + d13 + d14 + d15

Если при передаче изменится значение бита 8 (это как раз сам c3), 9, 10 .. 15 (а эти участвуют в вычислении c3), то вычисленное на приёмнике таким же образом c'3 не совпадет и -- ура -- третий бит синдрома равен 1.

Аналогично можно выделить область ответственности остальных контрольных битов.

c2 = d5 + d6 + d7 + d12 + d13 + d14 + d15

Потому что это синдромы из диапазонов 01002 -- 01112 и 11002 -- 11112 -- и второй бит у них установлен в 1.

c1 = d3 + d6 + d7 + d10 + d11 + d14 + d15

Это синдромы 00102, 00112, 01102, 01112, 10102, 10112, 11102, 11112.

И наконец

c0 = d3 + d5 + d7 + d9 + d11 + d13 + d15

А это просто младший бит, т.е. все нечетные синдромы.
Обобщить этот пример и получить классический код Хэмминга довольно несложно.

Если по честному, то к ci относятся номера из диапазона [2i, 2i+1) и далее от такого же диапазона, смещенного на 2i+1, потом ещё на 2i+1 и т.п.
Если по хардкору, то можно даже как-то так: c[i] = sum(d[j] for j in range(i+1, n) if j & (1 << i)) % 2

Вот собственно и всё.


Теперь вы знаете, как работает код Хэмминга. Если же ещё хочется понять, какого черта о нём написано в википедии, читайте дальше.

[приложения: то же, но без сравнений; пример; матрицы; обобщение; несколько ошибок]
Appendix A: Отказываемся от сравнений
Мне кажется, со сравнениями понятнее, но в других местах это описывают без них, и определенный смысл в этом есть, так что надо как-то объяснить...

Выше была предложена следующая модель вычисления синдрома:
- по полученным данным приемник вычисляет свои контрольные биты c'0..c'k
- сравнивает их с полученными контрольными битами c0..ck
- если c'i != ci, то i-й бит синдрома si устанавливается в 1.

Первое, что тут можно упростить это собственно сравнение. Так как сложение по модулю 2 одинаковых значений дает 0, а разных -- 1, вместо сравнения можно написать

si = c'i + ci

Дальше, поскольку c'i вычисляется на приёмнике по формуле вида c'i = dk + dr + ... + dp, это выражение можно подставить и получить

si = ci + dk + dr + ... + dp

То есть, поскольку ci должен дополнять до четности биты dk, dr, ..., dp, бит si будет равен 1, если контроль четности не проходит, то есть, если некорректно передан либо один из битов dk, dr, ..., dp, либо сам бит ci. Это в точности то, что нам надо.

Appendix B: Пример
Ну, куда же без примера.

10010110100 -- исходные данные
сс1с001с0110100 -- напихали контрольных битов

c0c113c2050617c309110111012113014015 -- и все пронумеровали для ясности

Теперь вычисляем контрольные биты:
с3 = 09 + 110 + 111 + 012 + 113 + 014 + 015 = 3 = 1
с2 = 05 + 06 + 17 + 012 + 113 + 014 + 015 = 2 = 0
с1 = 13 + 06 + 17 + 110 + 111 + 014 + 015 = 4 = 0
с0 = 13 + 05 + 17 + 09 + 111 + 113 + 015 = 4 = 0

001000110110100 -- итого
001001110110100 -- изменим шестой бит

Заново вычисляем контрольные биты

с'3 = 09 + 110 + 111 + 012 + 113 + 014 + 015 = 3 = 1
с'2 = 05 + 16 + 17 + 012 + 113 + 014 + 015 = 3 = 1
с'1 = 13 + 16 + 17 + 110 + 111 + 014 + 015 = 5 = 1
с'0 = 13 + 05 + 17 + 09 + 111 + 113 + 015 = 4 = 0

В результате c'1 != c1 и c'2 != c2, то есть синдром равен 01102 = 6. Магия!

Appendix C: причем тут матрицы
Посмотрим на преобразование "туда", т.е. кодирование. На входе битовый вектор длины n, на выходе битовый вектор длины m, m > n (добавились контрольные биты). Каждый бит выходного вектора либо просто равен соответствующему биту входного, либо получается как линейная комбинация нескольких входных битов. Это выглядит как работа для матрицы!

Конечно, это можно так записать, взять матрицу m*n, умножить её на вектор длины n и получить закодированный вектор. Строки матрицы, соответствующие информационным битам содержат только одну 1, строки матрицы, соответствующие контрольным -- несколько единиц, те, которые нужны по формуле.

Теперь вычисление синдрома. На входе битовый вектор длины m, на выходе вектор длины m-n, и, как понятно после Приложения A, все биты выходного вектора и тут получаются как линейные комбинации входного. То есть это тоже работа для матрицы. И вот это будет как раз та матрица, которую везде рисуют.

Если изобразить зоны ответственности контрольных битов в виде таблички, она окажется примерно такой (такой, с точностью до перестановок строк):

c0c13c2567c39101112131415
ответственность с0++++++++
ответственность с1++++++++
ответственность с2++++++++
ответственность с3++++++++


теперь осталось заменить + на 1, а в пустые места поставить 0, и это будет в точности матрица, на которую нужно умножить полученный вектор, чтобы вычислить синдром.

Appendix D: обобщаем
На эту матрицу можно посмотреть с другой стороны. Каждый столбец соответствует одному биту вектора. При изменении этого бита окажутся затронуты -- то есть, равны 1 -- те биты синдрома, которые за него "отвечают". То есть, фактически, в столбце под битом номер i записан синдром, который мы получим при изменении этого бита.

И теперь можно раскрутить всё в обратную сторону!

a) Взять матрицу правильного размера, выбрать, где там будут контрольные биты, написать под каждым битом симпатичный синдром -- готово, это будет матрица получения синдрома.
b) По ней понять, что за формулы соответствуют контрольным битам. Этот пункт накладывает ограничения на предыдущий. Формулы для одних контрольных битов не должны включать другие контрольные биты, т.к. их нет в исходном векторе. Это значит, что соответствующий контрольному биту синдром должен состоять из одной единички -- его самого.
с) По ним уже, если хочется, можно сделать матрицу преобразования, тоже поставив в ней контрольные биты на выбранные места.

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

В общем, это не рокет сайнс, конечно, и вроде бы можно эту идею и сразу понять. Но почему-то у меня до сих пор "сразу" не получалось. А сейчас получилось :)

Appendix E: если ошибок больше
Понятно, что происходит, если ошибка не одна. Каждый изменившийся бит меняет те биты синдрома, которые отмечены в его столбце. Если битов изменилось несколько, в результате получится побитовая сумма соответствующих им синдромов. Если все синдромы в матрице уникальны, то никакие два при побитовой сумме не дадут 0, а значит двойную ошибку можно обнаружить, хотя и не исправить. Тройную уже не обязательно, как повезёт.

Обычно говорят, что код Хэмминга позволяет исправить одинарную и обнаружить двойную. Мне кажется, точнее было бы сказать "или". Потому что он не позволяет отличить двойную от одинарной, по синдрому не понятно, можем ли мы это исправить, или нет, это решение, которое нужно принять заранее: либо всё исправляем (и возможно попытаемся исправить лишнее), либо всё замечаем (и не исправляем даже то, что могли бы).

И, кстати, интересный нетривиальный результат: из соображений расстояния Хэмминга (я про это не писал тут, почитайте сами, там просто) возможен код, который умеет замечать одну и две ошибки, но не умеет исправлять, и он должен быть экономнее, чем код Хэмминга. Но при выбранном подходе не получается сэкономить и замечать две ошибки. Потому что если у нас в матрице есть два одинаковых столбца, то ошибка в этих двух битах даст нулевой синдром и мы её не обнаружим. А если все столбцы уникальные, то это аналог Хэмминга, мы уже можем и исправлять... То есть такой код должен строиться по каким-то другим принципам, он уже не может укладываться в линейные комбинации битов и матрицы.
wall

Пример: lzo1x

Нельзя просто так взять и написать lzo!

Продолжаем тему LZ-алгоритмов и LZ-архиваторов. Совсем другой архиватор.

LZO это библиотека алгоритмов архивирования, написанных с прицелом на максимальную скорость работы. Название расшифровывается как Lempel-Ziv-Oberhumer; Markus Franz Xaver Oberhumer -- автор LZO. Алгоритмов я насчитал 39, форматов в которые они сохраняю данные – 9 (я считал по экспортируемым функциям; вот здесь в середине есть табличка, правда там только 37 алгоритмов). И всё это не описано нигде кроме исходного кода, о котором автор честно пишет:

Be warned: the main source code in the 'src' directory is a real pain to understand as I've experimented with hundreds of slightly different versions. It contains many #if and some gotos, and is *completely optimized for speed* and not for readability. Code sharing of the different algorithms is implemented by stressing the preprocessor - this can be really confusing. Lots of marcos and assertions don't make things better.

Подтверждаю, всё правда, но всё-таки не ужас-ужас-ужас, в чём-то разобраться можно. А из алгоритмов автор советует пользоваться lzo1x-1 либо lzo1x-999, второй сжимает несколько медленнее, но лучше.

Чтобы не возиться с C, можно использовать обёртку python-lzo, она реализована следующим образом.

Collapse )
Т.е. как раз эти два алгоритма.

Декомпрессор

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

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

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

  • признак конца данных это тоже такое специальное совпадение

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

  • после каждого блока открытого текста обязательно идёт совпадение, либо одно из обычных, либо специальное трехсимвольное совпадение

И ещё две оптимизации, влияющие на кодирование:
  • поскольку первым блоком совпадение быть не может (это вариант без предустановленного словаря, не с чем пока совпадать), длина первого блока может (но не обязана) кодироваться немного иначе, чем обычно

  • если у совпадения есть хвост, т.е. если после него идёт 1-3 байта открытого текста, то дальше не может быть блок открытого текста, только следующее совпадение.

Немножко запутано. Дальше будет хуже.

Collapse )

Collapse )

Collapse )

Код

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

Collapse )
wall

Осциллографы

Все про новый год, а я -- про осциллографы :) Отдаю долги старого.
Если кто-то ещё помнит, я раз в неделю хожу в политех и веду там лабы... Про них, родимых, и хочется написать.

Collapse )

Ну и ещё три лабы примерно в том же духе. Когда осваивал в сентябре-октябре -- очень интересно было, почти ничего ничего этого я не знал. Хотя когда-то, года три назад, тоже это всё сдавал.