Multi-table distribution encoding

A method for use with a computing system, the method comprising:

• storing, in memory:
• a plurality of encoded sub-blocks of an encoded matrix block, wherein each of the encoded sub-blocks includes a plurality of element indices;
• a plurality of lookup tables that each include a respective plurality of centroid values;
• and
• a table index array including a plurality of table indices that specify respective lookup tables associated with the encoded sub-blocks;
• and
• during a decoding stage:
• for each of the encoded sub-blocks:
• retrieving the table index of the encoded sub-block;
• retrieving the lookup table specified by the table index of the encoded sub-block;
• retrieving the element indices included in the encoded sub-block;
• and
• performing a plurality of table lookup operations using the table index, the lookup table, and the element indices to compute a decoded sub-block that includes, for each of the element indices included in the encoded sub-block, the corresponding centroid value specified by that element index;
• and
• outputting a decoded matrix block including the decoded sub-blocks computed from each of the encoded sub-blocks.

A computing system comprising:

• one or more processing devices configured to perform multi-table distribution encoding at least in part by:
• receiving an initial matrix block including a plurality of initial sub-blocks, wherein the initial sub-blocks each include a plurality of initial matrix elements;
• computing an encoded matrix block including a plurality of encoded sub-blocks at least in part by iteratively updating a table index array, a plurality of lookup tables, and the plurality of encoded sub-blocks, wherein:
• the plurality of lookup tables each include a respective plurality of centroid values;
• each of the centroid values is computed at least in part by performing one-dimensional k-means clustering on the plurality of initial matrix elements included in the initial sub-blocks;
• the table index array includes a plurality of table indices that specify respective lookup tables associated with the encoded sub-blocks;
• the table index array maps two or more of the encoded sub-blocks to a shared lookup table;
• and
• each of the encoded sub-blocks includes a plurality of element indices that specify respective centroid values of the plurality of centroid values;
• and
• outputting the encoded matrix block, the plurality of lookup tables, and the table index array.