Entropy coding and decoding using polar codes

摘要

Technologies are described herein for compressing or decompressing data using polar codes. Some example technologies may receive a data string comprising a first set of symbols. The technologies may transform the data string into a generalized message comprising a second set of symbols by mapping the data string to the generalized message via an inverse of a transformation function. The technologies may identify, based on a polar code, fixed symbols of the generalized message. The technologies may generate a compressed data string by extracting the fixed symbols from the generalized message and concatenating the fixed symbols into the compressed data string. As a result, the generalized message may be transformed into the compressed data string.

主权项

1. A method for compressing and decompressing data, the method comprising:
receiving a data string comprising a first set of symbols; transforming the data string into a generalized message comprising a second set of symbols by mapping the data string to the generalized message via an inverse of a transformation function; identifying, based on a polar code, fixed symbols of the generalized message; generating a compressed data string by extracting the fixed symbols from the generalized message and concatenating the fixed symbols into the compressed data string, thereby transforming the generalized message into the compressed data string; transforming the compressed data string into a recovered data string based on the polar code, wherein transforming the compressed data string into the recovered data string comprises:
defining a base data string comprising zero values; andperforming a polar decoding on the base data string to identify free symbols in a recovered generalized message; and verifying that the recovered data string matches the data string based on the polar code.