Compression and decompression of fixed length data structures

Patent metadata

Field	Value
Publication number	US-10958286-B2
Application number	US-202016794975-A
Country	US
Kind code	B2
Filing date	Feb 19, 2020
Priority date	Feb 20, 2019
Publication date	Mar 23, 2021
Grant date	Mar 23, 2021

Abstract

A method of encoding fixed length data bit strings includes receiving and sequentially encoding a sequence of data bit strings. For a data bit string immediately following a preceding data bit string, this includes obtaining a reference bit string, and a mask bit string and a tracking bit string as present at the end of a previous encoding of the preceding data bit string, identifying bits that differ form corresponding bits in the reference bit string, determining, as unpredictable bits, all those bits in the data bit string that are indicated as not predictable by the mask bit string and are not in bit positions indicated by the tracking bit string, generating a sequence of position indicators, generating an encoded data packet that includes representations of values of the unpredictable bits and the sequence of positon indicators, and periodically updating the mask bit string and the tracking bit string.

First claim

The invention claimed is:

1. A method of encoding fixed length data bit strings, the method comprising:
receiving a sequence of data bit strings; and
sequentially encoding the data bit strings,
wherein sequentially encoding the data bit strings comprises, for a data bit string immediately following a preceding data bit string in the sequence of data bit strings:
obtaining a reference bit string for the data bit string, wherein the reference bit string corresponds to said preceding data bit string;
obtaining a mask bit string and a tracking bit string as present at the end of a previous encoding of the preceding data bit string, wherein the mask bit string is indicative of which bits in the data bit strings are predictable, and which bits in the data bit string are not predictable, in the sense that predictable bits in the data bit string immediately following the preceding data bit string have a high probability of being in the same state as those in the reference bit string, and wherein the tracking bit string is indicative of which bits in the mask bit string have recently changed;
identifying bits in the data bit string that differ from corresponding bits in the reference bit string;
determining, as unpredictable bits, all those bits in the data bit string that are indicated as not predictable by the mask bit string and that are not in bit positions indicated by the tracking bit string;
generating, for those bits among the identified bits that are not among the unpredictable bits, a sequence of position indicators, each position indicator indicating a bit position of a respective bit with respect to a bit position indicated by the preceding position indicator in the sequence of position indicators, such that the position indicators corresponding to bit positions indicated by the tracking bit string are encoded with a reference to the tracking bit string;
generating an encoded data packet for the data bit string, wherein the encoded data packet includes a representation of values of the unpredictable bits and a representation of the sequence of position indicators; and
periodically updating the mask bit string and the tracking bit string.

2. The method according to claim 1 , wherein the sequence of position indicators includes first-type position indicators relating to the bits among the identified bits that are indicated by the tracking bit string and second-type position indicators relating to bits among the identified bits that are not indicated by the tracking bit string, and wherein the first-type position indicators indicate respective bit positions in terms of a number of set bits in the tracking bit string located between the bit position indicated by the preceding position indicator in the sequence of position indicators and the respective bit position.

3. The method according to claim 1 , further comprising:
maintaining a mask update bit string that indicates, for a current period, all bits in the data bit strings encoded during that period that have been identified as bits that differ from corresponding bits in the respective reference bit strings.

4. The method according to claim 3 , further comprising, when updating the mask bit string:
generating, as part of the sequence of position indicators, one or more third-type position indicators, wherein each third-type position indicator indicates a respective bit within the data bit string that is indicated by the mask bit string and that is not indicated by any of the mask update bit string or the tracking bit string; and
setting the mask bit string to the mask update bit string.

5. The method according to claim 3 , further comprising, when updating the tracking bit string:
setting the tracking bit string to indicate all those bits that are indicated by the mask bit string but not indicated by the mask update bit string, and to indicate all those bits that are indicated by the mask update bit string but not indicated by the mask bit string.

6. The method according to claim 1 , further comprising:
updating the tracking bit string to also indicate bit positions of the identified bits in the data bit string that differ from corresponding bits in the reference bit string and are not indicated by the mask bit string.

7. A method of sequentially decoding a plurality of encoded data packets into corresponding decoded fixed length data bit strings,
wherein each encoded data packet corresponds to a data bit string immediately following a preceding data bit string in a sequence of data bit strings and includes a representation of values of unpredictable bits in the respective data bit string and a representation of a sequence of position indicators; and
wherein sequentially decoding the encoded data packets comprises, for an encoded data packet:
obtaining a reference bit string for the corresponding data bit string, wherein the reference bit string corresponds to said preceding data bit string;
obtaining the mask bit string, and the tracking bit string for the encoded data packet as present at the end of a previous decoding of the preceding data bit string, wherein the mask bit sting is indicative of which bits in the data bit strings are predictable, and which bits in the data bit string are not predictable, in the sense that predictable bits in the data bit string immediately following the preceding data bit string have a high probability of being in the same stat as those in the reference bit string, and wherein the tracking bit string is indicative of which bits in the mask bit string have recently changed;
decoding the sequence of position indicators from the encoded data packet, wherein the position indicators indicate bit positions of difference bits in the respective data bit string that differ from corresponding bits in a reference bit string for the respective data bit string, and wherein each position indicator indicates a bit position of a respective difference bit with respect to a bit position indicated by the preceding position indicator in the sequence of position indicators, wherein position indicators that indicate bit positions of respective difference bits that are indicated by the tracking bit string encode the bit position with reference to the tracking bit string;
decoding the values of the unpredictable bits from the encoded data packet, wherein the unpredictable bits are all those bits in the respective data bit string that are indicated as not predictable by the mask bit string and that are not in bit positons indicated by a tracking bit string;
setting the data bit string to be identical to the reference bit string;
inverting all those bits in the data bit string that are indicated by the position indicators in the sequence of position indicators but not indicated by any of the mask bit string or the tracking bit string;
inverting all those bits in the data bit string that are indicated by the position indicators in the sequence of position indicators and indicated by the tracking bit string;
inserting the values of the unpredictable bits in sequence into the data bit string in respective bit positions indicated by the mask bit string but not indicated by the tracking bit string, unless these bit positions are indicated by position indicators in the sequence of position indicators, wherein bits in respective bit positions of the data bit string are replaced by the values of respective unpredictable bits;
outputting the data bit string; and
periodically updating the mask bit string and periodically updating the tracking bit string.

8. The method according to claim 7 , further comprising:
updating the tracking bit string to further indicate all those bits whose bit positions are indicated by those position indicators that do not encode the bit position wi

Assignees

• ESA

Inventors

• Evans David

Classifications

• H03M7/3066 Primary

  by means of a mask or a bit-map · CPC title

• H03M7/6011

  Encoder aspects · CPC title

• H03M7/30 Primary

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• H04L69/04

  Protocols for data compression, e.g. ROHC · CPC title