Hamming

KO | EN

gitlite — search

#hacktoberfest #react #typescript #go #android #machine-learning #rust #deep-learning #nodejs #awesome #awesome-list #mcp #openai #open-source

(★ 16)

Библиотека для упаковки и распаковки данных по алгоритму Хэмминга (избыточные данные для восстановления)

Hamming Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

[![latest](https://img.shields.io/github/v/release/GyverLibs/Hamming.svg?color=brightgreen)](https://github.com/GyverLibs/Hamming/releases/latest/download/Hamming.zip)
[![PIO](https://badges.registry.platformio.org/packages/gyverlibs/library/Hamming.svg)](https://registry.platformio.org/libraries/gyverlibs/Hamming)
[![Foo](https://img.shields.io/badge/Website-AlexGyver.ru-blue.svg?style=flat-square)](https://alexgyver.ru/)
[![Foo](https://img.shields.io/badge/%E2%82%BD%24%E2%82%AC%20%D0%9F%D0%BE%D0%B4%D0%B4%D0%B5%D1%80%D0%B6%D0%B0%D1%82%D1%8C-%D0%B0%D0%B2%D1%82%D0%BE%D1%80%D0%B0-orange.svg?style=flat-square)](https://alexgyver.ru/support_alex/)
[![Foo](https://img.shields.io/badge/README-ENGLISH-blueviolet.svg?style=flat-square)](https://github-com.translate.goog/GyverLibs/Hamming?_x_tr_sl=ru&_x_tr_tl=en)

[![Foo](https://img.shields.io/badge/ПОДПИСАТЬСЯ-НА%20ОБНОВЛЕНИЯ-brightgreen.svg?style=social&logo=telegram&color=blue)](https://t.me/GyverLibs)

# Hamming
Библиотека для упаковки и распаковки данных по алгоритму Хэмминга (Extended Hamming)
- Порядок алгоритма (кол-во бит Хэмминга) 3-7
- Восстановление данных, повреждённых при пересылке: восстановление 1 бита на блок, либо определение невозможности восстановления
- Опционально перемешивание данных для более надёжной передачи - может восстановить несколько испорченных бит/байт подряд

> Библиотека обновлена до версии v2, несовместима со старой! Старую версию можно подключить как `#include <HammingOld.h>`

### Совместимость
Совместима со всеми Arduino платформами (используются Arduino-функции)

## Содержание
- [Документация](#doc)
- [Пример](#example)
- [Версии](#versions)
- [Установка](#install)
- [Баги и обратная связь](#feedback)

## Документация
### База
Новая версия библиотеки содержит несколько классов по количеству избыточных данных пакета:

| Класс      | Размер блока, байт | Размер блока, бит | Данных в блоке, бит | Размер пакета 100 байт, байт |
| ---------- | ------------------ | ----------------- | ------------------- | ---------------------------- |
| `Hamming3` | 1                  | 8                 | 4                   | 200                          |
| `Hamming4` | 2                  | 16                | 11                  | 146                          |
| `Hamming5` | 4                  | 32                | 26                  | 124                          |
| `Hamming6` | 8                  | 64                | 57                  | 120                          |
| `Hamming7` | 16                 | 128               | 120                 | 112                          |

Чем выше класс, тем:

- Больше размер блока (минимальный размер пакета)
- Меньше итоговый размер пакета, т.к. выше соотношение битов данных к размеру блока
- Дольше обработка и ниже надёжность

### Бенчмарк
Тест проводился на AVR ATmega328p 16MHz, время в мкс.

#### Hamming4
| Размер пакета | `encode` | `mix` | `mix8` | `decode` |
| ------------- | -------- | ----- | ------ | -------- |
| 25            | 1673     | 1557  | 486    | 2811     |
| 50            | 3315     | 3034  | 1078   | 5469     |
| 100           | 7240     | 5977  | 2185   | 10794    |

> Версии 4/5/6/7 не сильно отличаются по времени

#### Hamming3
| Размер пакета | `encode` | `mix` | `mix8` | `decode` |
| ------------- | -------- | ----- | ------ | -------- |
| 25            | 94       | 1933  | 689    | 230      |
| 50            | 185      | 3847  | 1373   | 472      |
| 100           | 366      | 7690  | 2741   | 944      |

> `Hamming3` реализован таблично и работает многократно быстрее остальных

### Функции
```cpp
// размер запакованных данных по размеру исходных
size_t encodedSize(size_t size);

// размер распакованных данных по размеру запакованных. 0 - некорректный размер пакета
size_t decodedSize(size_t size);

// замешать запакованные данные. false если ошибка аллокации
bool mix(void* pack, size_t size);

// размешать запакованные данные. false если ошибка аллокации
bool unmix(void* pack, size_t size);

// замешать запакованные данные. false если ошибка аллокации
bool mix8(void* pack, size_t size);

// размешать запакованные данные. false если ошибка аллокации
bool unmix8(void* pack, size_t size);

// Запаковать данные во внешний буфер dest размера encodedSize() [должен быть инициализирован 0]
void encode(void* dest, const void* src, size_t size);

// Распаковать данные в себя. Вернёт true, если распакованы без ошибок или ошибки исправлены
bool decode(void* src, size_t size);
```

### Использование
- Взяли данные, получили размер буфера (больше чем сами данные), закодировали данные в него
- "Передали" буфер на другое устройство
- Раскодировали полученные данные. Если в процессе передачи данные были повреждены - они будут сами по возможности восстановлены

> [!CAUTION]
> Так как после кодирования пакет имеет размер, кратный размеру блока при выбранном порядке, то реальный размер пакета будет утерян - при распаковке он посчитается математически. Например `Hamming5`, размер данных 10 байт. Размер пакета получится 16 байт (округлится в большую сторону), а при распаковке получится 13 байт. Реальный размер пакета нужно знать на стороне приёмника или добавить в сам пакет, библиотека этого не делает.

### Надёжность
Алгоритм может восстановить один "испорченный" бит в блоке. Чем меньше размер блока, тем больший "шум" потенциально сможет пережить пакет при передаче. Блоки идут друг за другом, поэтому если повредить два соседних бита в пределах одного блока - данные восстановить не получится.

В режиме `Hamming3` пакет занимает размер двойных данных, т.е. это как отправить данные дважды. Но при наличии помех данные будут просто испорчены, сколько пакетов не отправляй. А с Hamming можно потерять приличную часть пакета (12.5% в данном случае) и данные получится восстановить.

> При создании своих протоколов связи рекомендуется добавлять в пакет CRC и размер пакета, как например в библиотеке [GyverWire](https://github.com/GyverLibs/GyverWire)

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

Доступно два алгоритма перемешивания - полный `mix`/`unmix` и 8-байтный `mix8`/`unmix8`. Полный выполняется долго и полностью растягивает блоки по пакету. 8-байтный работает блоками по 8 байт, остаток замешивает по остатку. Полное перемешивание позволяет восстановить несколько испорченных байт подряд (при большом размере пакета), а 8-битное - только 1 байт на каждые 8 байт. С одиночными испорченными битами они работают одинаково.

## Пример
```cpp
#include <Hamming.h>

void setup() {
    Serial.begin(115200);
    Serial.println("=== START ===");

// создали дату (любой тип)
    char str[] = "Hello, world! Hamming encoding";

Serial.print("data len: "), Serial.println(sizeof(str));

// размер запакованных данных
    size_t elen = Hamming4::encodedSize(sizeof(str));

Serial.print("pack len: "), Serial.println(elen);

// буфер для пакета
    uint8_t p[elen] = {};

// упаковка
    Hamming4::encode(p, str, sizeof(str));

// замешивание
    Hamming4::mix8(p, elen);
    // Hamming4::mix(p, elen);

// ======== ПЕРЕДАЧА ========
    // имитация порчи данных

p[3] = 0;  // байт
    // bitWrite(p[9], 3, !bitRead(p[9], 3));  // бит

// ======== ПЕРЕДАЧА ========

// размешивание
    Hamming4::unmix8(p, elen);
    // Hamming4::unmix(p, elen);

// размер распакованных данных
    size_t dlen = Hamming4::decodedSize(sizeof(p));

Serial.print("decode len: "), Serial.println(dlen);

// распаковка (в этот же буфер)
    bool res = Hamming4::decode(p, sizeof(p));

if (res) Serial.write((char*)p, dlen), Serial.println();
    else Serial.println("Data error!");

Serial.println("==== END ====");
}
```

## Версии
- v1.0
- v1.1 - исправлена критическая ошибка
- v1.2 - добавлена bool pack(uint8_t *ptr, uint32_t size)
- v1.3 - исправлена критическая ошибка
- v1.3.1 - мелкие улучшения
- v2.0.0 - сильная оптимизация скорости и памяти, новые инструменты

## Установка
- Библиотеку можно найти по названию **Hamming** и установить через менеджер библиотек в:
    - Arduino IDE
    - Arduino IDE v2
    - PlatformIO
- [Скачать библиотеку](https://github.com/GyverLibs/Hamming/archive/refs/heads/main.zip) .zip архивом для ручной установки:
    - Распаковать и положить в *C:\Program Files (x86)\Arduino\libraries* (Windows x64)
    - Распаковать и положить в *C:\Program Files\Arduino\libraries* (Windows x32)
    - Распаковать и положить в *Документы/Arduino/libraries/*
    - (Arduino IDE) автоматическая установка из .zip: *Скетч/Подключить библиотеку/Добавить .ZIP библиотеку…* и указать скачанный архив
- Читай более подробную инструкцию по установке библиотек [здесь](https://alexgyver.ru/arduino-first/#%D0%A3%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B1%D0%B8%D0%B1%D0%BB%D0%B8%D0%BE%D1%82%D0%B5%D0%BA)
### Обновление
- Рекомендую всегда обновлять библиотеку: в новых версиях исправляются ошибки и баги, а также проводится оптимизация и добавляются новые фичи
- Через менеджер библиотек IDE: найти библиотеку как при установке и нажать "Обновить"
- Вручную: **удалить папку со старой версией**, а затем положить на её место новую. "Замену" делать нельзя: иногда в новых версиях удаляются файлы, которые останутся при замене и могут привести к ошибкам!

## Баги и обратная связь
При нахождении багов создавайте **Issue**, а лучше сразу пишите на почту [alex@alexgyver.ru](mailto:alex@alexgyver.ru)  
Библиотека открыта для доработки и ваших **Pull Request**'ов!

При сообщении о багах или некорректной работе библиотеки нужно обязательно указывать:
- Версия библиотеки
- Какой используется МК
- Версия SDK (для ESP)
- Версия Arduino IDE
- Корректно ли работают ли встроенные примеры, в которых используются функции и конструкции, приводящие к багу в вашем коде
- Какой код загружался, какая работа от него ожидалась и как он работает в реальности
- В идеале приложить минимальный код, в котором наблюдается баг. Не полотно из тысячи строк, а минимальный код

Hamming

Hamming Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Hamming

Hamming Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README