Библиотека для упаковки и распаковки данных по алгоритму Хэмминга (Extended Hamming)
- Порядок алгоритма (кол-во бит Хэмминга) 3-7
- Восстановление данных, повреждённых при пересылке: восстановление 1 бита на блок, либо определение невозможности восстановления
- Опционально перемешивание данных для более надёжной передачи - может восстановить несколько испорченных бит/байт подряд
Библиотека обновлена до версии v2, несовместима со старой! Старую версию можно подключить как
#include <HammingOld.h>
Совместима со всеми Arduino платформами (используются Arduino-функции)
Новая версия библиотеки содержит несколько классов по количеству избыточных данных пакета:
| Класс | Размер блока, байт | Размер блока, бит | Данных в блоке, бит | Размер пакета 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, время в мкс.
| Размер пакета | encode |
mix |
mix8 |
decode |
|---|---|---|---|---|
| 25 | 1673 | 1557 | 486 | 2811 |
| 50 | 3315 | 3034 | 1078 | 5469 |
| 100 | 7240 | 5977 | 2185 | 10794 |
Версии 4/5/6/7 не сильно отличаются по времени
| Размер пакета | encode |
mix |
mix8 |
decode |
|---|---|---|---|---|
| 25 | 94 | 1933 | 689 | 230 |
| 50 | 185 | 3847 | 1373 | 472 |
| 100 | 366 | 7690 | 2741 | 944 |
Hamming3реализован таблично и работает многократно быстрее остальных
// размер запакованных данных по размеру исходных
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
Если "перемешать" пакет (расположить биты блоков по очереди друг за другом), то после размешивания можно восстановить несколько испорченных бит подряд, или даже байтов - зависит от размера пакета, т.к. ошибка затронет разные блоки. Пакет перемешивается после упаковки (перед отправкой) и размешивается обратно (после получения) перед распаковкой. Перемешивание и размешивание пакета - долгая операция и выделяет память размером с буфер, добавляется вручную на усмотрение пользователя.
Доступно два алгоритма перемешивания - полный mix/unmix и 8-байтный mix8/unmix8. Полный выполняется долго и полностью растягивает блоки по пакету. 8-байтный работает блоками по 8 байт, остаток замешивает по остатку. Полное перемешивание позволяет восстановить несколько испорченных байт подряд (при большом размере пакета), а 8-битное - только 1 байт на каждые 8 байт. С одиночными испорченными битами они работают одинаково.
#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
- Скачать библиотеку .zip архивом для ручной установки:
- Распаковать и положить в C:\Program Files (x86)\Arduino\libraries (Windows x64)
- Распаковать и положить в C:\Program Files\Arduino\libraries (Windows x32)
- Распаковать и положить в Документы/Arduino/libraries/
- (Arduino IDE) автоматическая установка из .zip: Скетч/Подключить библиотеку/Добавить .ZIP библиотеку… и указать скачанный архив
- Читай более подробную инструкцию по установке библиотек здесь
- Рекомендую всегда обновлять библиотеку: в новых версиях исправляются ошибки и баги, а также проводится оптимизация и добавляются новые фичи
- Через менеджер библиотек IDE: найти библиотеку как при установке и нажать "Обновить"
- Вручную: удалить папку со старой версией, а затем положить на её место новую. "Замену" делать нельзя: иногда в новых версиях удаляются файлы, которые останутся при замене и могут привести к ошибкам!
При нахождении багов создавайте Issue, а лучше сразу пишите на почту alex@alexgyver.ru
Библиотека открыта для доработки и ваших Pull Request'ов!
При сообщении о багах или некорректной работе библиотеки нужно обязательно указывать:
- Версия библиотеки
- Какой используется МК
- Версия SDK (для ESP)
- Версия Arduino IDE
- Корректно ли работают ли встроенные примеры, в которых используются функции и конструкции, приводящие к багу в вашем коде
- Какой код загружался, какая работа от него ожидалась и как он работает в реальности
- В идеале приложить минимальный код, в котором наблюдается баг. Не полотно из тысячи строк, а минимальный код