Huffman coding

Post Reply
mnfisher
Valued Contributor
Posts: 399
http://meble-kuchenne.info.pl
Joined: Wed Dec 09, 2020 9:37 pm
Has thanked: 49 times
Been thanked: 227 times

Huffman coding

Post by mnfisher »

Having recently had a chat about transmitting data over Bluetooth - I had the idea of compressing the data first - this minimizes the amount of data transmitted and, particularly on slow connections (LORA), can make transmission quicker. And being at a loose end....

I used Huffman encoding - and in the demo here (for esp32 - but works well in simulation) - reduces the size of the transmitted data from 560 bits to 230 (note there is also some 'overhead' added to transmission - parity / stop bits etc)

I was pleased how easily the algorithm fitted onto Flowcode - although the lack of memory allocation is a bit of a workaround (I used an array holding 128 x 8 byte records - where each record is 'character', frequency, left and right nodes) - I could have saved memory by cutting the size of the char and left/right fields at the expense of a little less clarity in the code. (With a little work this would fit on Arduino with 2k RAM)

Currently it generates a binary 'string' - though for use (in the real world) it should generate a binary block of data - this is left as an exercise :-)
Huffman.fcfx
(43.14 KiB) Downloaded 36 times
Note - if you want to encode longer strings - you'll need to enlarge 'str' in main - or alter encode to output directly to UART or add to a data block and send the data as 1k (or other) blocks with a checksum.... Note that the 'sender' and 'receiver' also need to have the same lookup table (so for 'text' this would be created by adding a known 'text' (say the text of a book - or using letter frequency tables for a language) to the frequency table)

Martin

Post Reply