Data compression and storage

Patent metadata

Field	Value
Publication number	US-10972126-B2
Application number	US-201916698687-A
Country	US
Kind code	B2
Filing date	Nov 27, 2019
Priority date	Nov 30, 2018
Publication date	Apr 6, 2021
Grant date	Apr 6, 2021

Abstract

A data compression method comprises encoding groups of data items by generating, for each group, header data comprising h-bits and a plurality of body portions each comprising b-bits and each body portion corresponding to a data item in the group. The value of h may be fixed for all groups and the value of b is fixed within a group, wherein the header data for a group comprises an indication of b for the body portions of that group. In various examples, b=0 and so there are no body portions. In examples where b is not equal to zero, a body data field is generated for each group by interleaving bits from the body portions corresponding to data items in the group. The resultant encoded data block, comprising the header data and, where present, the body data field can be written to memory.

First claim

What is claimed is:

1. A method of data compression, comprising:
receiving a plurality of data items;
encoding groups of data items by generating, for each of the groups, header data comprising h bits and a plurality of body portions, each body portion comprising b bits and each of the body portions corresponding to a data item in the group, wherein b is fixed within a group and wherein the header data for a group comprises an indication of b for the body portions of that group;
generating, for each of the groups where b>0, a body data field for the group by interleaving bits from the body portions corresponding to data items in the group; and
storing one or more encoded data blocks comprising the header data and the body data fields.

2. The method according to claim 1 , wherein h is fixed for all groups and b is not fixed between groups.

3. The method according to claim 1 , wherein storing one or more encoded data blocks comprises:
storing a body data block comprising body data fields for a plurality of groups; and
storing a header data block comprising header data for the plurality of groups.

4. The method according to claim 1 , wherein interleaving bits from the body portions corresponding to data items in the group comprises:
(a) inserting a first bit from each of the body portions into the body data field;
(b) inserting a next bit from each of the body portions into the body data field; and
(c) repeating (b) until all bits from each of the body portions have been inserted into the body data field.

5. The method according to claim 4 , wherein inserting a first bit from each of the body portions into the body data field comprises inserting a least significant bit from each of the body portions into the body data field and wherein inserting a next bit from each of the body portions into the body data field comprises inserting a next least significant bit from each of the body portions into the body data field.

6. The method according to claim 1 , wherein encoding groups of data items comprises, for each of the groups:
receiving the group of data items;
identifying a body portion size, b, by locating a bit position of a most significant leading one across all the data items in the group;
generating the header data comprising a bit sequence encoding the body portion size; and
generating a body portion comprising b-bits for each of the data items in the group by removing none, one or more leading zeros from each data item.

7. The method according to claim 6 , wherein identifying a body portion size further comprises:
checking if the identified body portion size is a valid body portion size; and
in response to determining that the identified body portion size is not a valid body portion size, updating the body portion size to a next largest valid body portion size.

8. The method according to claim 7 , further comprising, prior to encoding groups of data items:
analysing a plurality of groups of data items to generate a set of valid body portion sizes.

9. The method according to claim 8 , wherein analysing a plurality of groups of data items to generate a set of valid body portion sizes comprises:
analysing the data items in the plurality of groups of data items to identify a body portion size for each of the plurality of groups;
identifying one or more least common body portion sizes for the plurality of groups of data items; and
generating the set of valid body portion sizes by removing from a set of all possible body portion sizes, those body portion sizes corresponding to the identified one or more least common body portion sizes.

10. The method according to claim 1 , wherein the data items comprise weights for a neural network.

11. The method according to claim 10 , wherein analysing a plurality of groups of data items to generate a set of valid body portion sizes comprises, for each layer in the neural network:
analysing all weights for the layer to generate a set of valid body portion sizes for that layer.

12. The method according to claim 1 ,
wherein the data items have a distribution centred substantially on zero and the method further comprises, prior to encoding a group of data items, pre-processing the data items in the group by converting all data items having a negative value to positive values and interleaving the converted data items with data items having a positive value, or
wherein the data items have a distribution centred on a non-zero value and the method further comprises, prior to encoding a group of data items, pre-processing the data items in the group by shifting all data items such that the shifted distribution is centred substantially on zero and then converting all shifted data items having a negative value to positive values and interleaving the converted shifted data items with shifted data items having a positive value.

13. A method of data decompression, comprising:
receiving one or more blocks of data, the one or more blocks of data encoding one or more groups of data items;
reading header data into a first buffer;
reading body data into a second buffer; and
for each of the encoded groups of data items:
reading header data for the group from the first buffer, wherein the header data for a group of data items comprises a h-bit indication of a b-bit body portion size for the group of data items, wherein b is fixed within a group;
determining the bit size b of the body portion for the group of data items from the header data;
reading a body data field from the second buffer based on the determined body portion size, the body data field comprising interleaved body portions, with one body portion for each of the data items in the group;
decoding the body data field to generate the decoded data items, the decoding comprising de-interleaving the body portions, wherein each of the decoded data items comprises n bits, where n≥b; and
outputting the decoded data items.

14. The method according to claim 13 , wherein h is fixed for all groups and b is not fixed between groups.

15. The method according to claim 13 , wherein the body data field comprises a plurality of concatenated sections, each of the sections comprising one bit from each body portion, and wherein decoding the body data field comprises:
starting with an initial set of data items comprising only zeros, one for each data item in the group, reading sections of the body data field and for each section of the body data field, overwriting one of the zeros for each of the data items with a bit value from the section of the body data field to generate the decoded data items; or
generating a body data mask comprising ones in bit positions corresponding to the determined body portion size, reading sections of the body data field and for each section of the body data field, combining one of the bits in the body data mask for each of the data items with a bit value from the section of body data field.

16. The method according to claim 15 , wherein the first section in the body data field comprises a least significant bit from each of the body portions, the subsequent section comprises a next least significant bit from each of the body portions and a last section in the body data field comprises a most significant bit from each of the body portions.

17. The method according to claim 13 , wherein the data items comprise weights for a neural network.

18. A data compression apparatus, comprising:
an input for receiving a plurality of data items;
an encoding module configured to encode groups of data items by generating, for each of the g

Assignees

• Imagination Tech Ltd

Inventors

• Fenney Simon
• Clark Greg
• Vines Alan

Classifications

• G06N3/0464

  Convolutional networks [CNN, ConvNet] · CPC title

• G06N3/0495

  Quantised networks; Sparse networks; Compressed networks · 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 Primary

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

• H03M7/4012

  Binary arithmetic codes · CPC title