# конспект · шаг 7 из 7
Конспект: код Грея, CRC и биты плавающей точки
Понятия
Код Грея - порядок всех 2ⁿ слов из n битов, в котором соседние слова отличаются одним битом.
Образующее число - делитель в CRC; остаток на бит короче него.
Пачка ошибок - несколько искажённых битов подряд.
Смещение порядка - число 1023, прибавленное к степени двойки, чтобы поле порядка было неотрицательным.
Z-порядок - нумерация клеток перемешиванием битов координат; кривая Гильберта - нумерация, в которой соседние номера всегда соседние клетки.
Что унести
КОД ГРЕЯ
в код: g = x ^ (x >> 1) 13 = 1101 → 1011
обратно: x = g ^ (g >> 1) ^ (g >> 2) ^ … 1011 → 1101
3 бита: 000 001 011 010 110 111 101 100 отражение: список, потом он же назад с единицей
шаг k меняет бит «число хвостовых нулей k»: 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0
двоичный счёт от 0 до 7: 11 переключений битов; код Грея: 7
перебор подмножеств с одной правкой: i = (k & −k).bit_length() − 1; переключить элемент i
12 чисел: 24 618 шагов против 135 213 правка должна быть обратимой: сумма да, минимум нет
CRC: ОСТАТОК ОТ ДЕЛЕНИЯ БЕЗ ПЕРЕНОСОВ
сложение = вычитание = ^ шаг на бит: сдвиг; если выдвинулась единица - ^ с образующим
1101 000 / 1011 → остаток 001 передают 1101 001; получатель делит всё и ждёт ноль
CRC-8, образующее 0x107: if crc & 0x80: crc = (crc << 1 ^ 0x07) & 0xFF else: crc = crc << 1
CRC-32, младшим битом вперёд: if crc & 1: crc = crc >> 1 ^ 0xEDB88320 else: crc = crc >> 1
начало 0xFFFFFFFF, в конце ^ 0xFFFFFFFF
эталон для «123456789»: CRC-8 = 0xF4, CRC-32 = 0xCBF43926
таблица на 256 значений: crc = tablica[crc ^ bajt] 400 байтов: 801 шаг против 10 403
| искажение | сумма байтов | CRC |
|---|---|---|
| один бит | видит | видит всегда |
| пачка не длиннее остатка | не всегда | видит всегда |
| два соседних байта переставлены | не видит | CRC-32 всегда; CRC-8 кроме a ^ b = 0xFD |
| +1 в одном байте, −1 в соседнем | не видит | CRC-32 всегда; CRC-8 в 94 случаях из 100 |
| намеренная подмена | не видит | не видит: crc(a ^ b) = crc(a) ^ crc(b) |
ДРОБНОЕ ЧИСЛО, 64 БИТА
знак: 1 бит порядок: 11 битов, смещение 1023 дробь: 52 бита
значение = (−1)ˢ · (1 + f / 2⁵²) · 2^(e − 1023) e от 1 до 2046
e = 0, f = 0 ноль, +0 и −0 e = 2047, f = 0 бесконечность
e = 0, f ≠ 0 малое число: f · 2⁻¹⁰⁷⁴ e = 2047, f ≠ 0 «не число»
число hi lo знак порядок степень
1,0 0x3FF00000 0 0 1023 0
−2,5 0xC0040000 0 1 1024 1
1 000 000 0x412E8480 0 0 1042 19
0,1 0x3FB99999 0x9999999A 0 1019 −4 дробь 1001 1001 … 1010
порядок = hi >> 20 & 0x7FF дробь = (hi & 0xFFFFF) << 32 | lo
значащих битов 53; шаг между соседями при степени p: 2^(p − 52)
целые точны до 2⁵³; дальше: 2⁵³, 2⁵³ + 2, 2⁵³ + 4
наименьшее положительное 2⁻¹⁰⁷⁴ ≈ 5 · 10⁻³²⁴; наименьшее обычное 2⁻¹⁰²² ≈ 2,2 · 10⁻³⁰⁸
ПЛОСКОСТЬ В ОДНОМ ЧИСЛЕ
Z-номер: биты x на чётных местах, биты y на нечётных (5, 3) → 011011 = 27
раздвинуть 16 битов: x = (x | x << 8) & 0x00FF00FF; << 4, 0x0F0F0F0F; << 2, 0x33333333; << 1, 0x55555555
z = razdvinut(x) | razdvinut(y) << 1
сетка 16 × 16 длина пути скачков самый длинный шаг
кривая Гильберта 255 0 1
Z-порядок 480 127 16
общее начало номера → общий квадрат: да, у обеих
соседние клетки → близкие номера: нет, ни у одной; запрос прямоугольника - несколько диапазонов
В Python: zlib.crc32(данные); math.frexp(x), x.hex(), math.isnan, math.isinf;
struct.pack(">d", x) - восемь байтов числа.
Ловушки джокера
Обратный перевод той же формулой. g ^ (g >> 1) не возвращает номер.
Арифметика над кодами Грея. Складывать и сравнивать можно только номера.
Код Грея на десять значений. Обрезанный код не замкнут; берут середину шестнадцатизначного.
CRC против подделки. Он линеен; для этого нужна подпись.
Разные «CRC-32». Образующее число, начало, порядок битов и финальный ^ должны совпасть; сверка по
строке «123456789».
Нулевое начало. Без начального значения из единиц ведущие нулевые байты не меняют CRC.
0.1 + 0.2 == 0.3. Ложно; дробные сравнивают с допуском.
Большое целое через дробное. 9 007 199 254 740 993 превращается в …992.
«Не число». Не равно себе, ломает сортировку и поиск.
Малое число по формуле обычного. У него нет неявной единицы; порядок определяет старшая единица дроби.
Проверка дроби только в hi. Единица может сидеть в младшем слове.
«Соседние Z-номера - значит рядом». Половина шагов Z-порядка - скачки.
Куда это ведёт
Раздел начался с шести операций и закончился тем, что три очень разные вещи - счётчик положения, контрольная сумма и дробное число - оказались конструкциями из битовых полей. Следующий раздел - случайность: хеш-функции, фильтр Блума, вероятностные счётчики. Они целиком стоят на масках, сдвигах, счёте единиц и ведущих нулей.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий