Compression circuits and methods using tree based encoding of bit masks

Patent metadata

Field	Value
Publication number	US-11942970-B2
Application number	US-202217687589-A
Country	US
Kind code	B2
Filing date	Mar 4, 2022
Priority date	Mar 4, 2022
Publication date	Mar 26, 2024
Grant date	Mar 26, 2024

Abstract

Embodiments of the present disclosure include techniques for compressing data using a tree encoded bit mask that may result in higher compression ratios. In one embodiment, an input vector having a plurality of values is received by a first plurality of switch circuits. Selection of the input values is controlled by sets of bits from the bit mask. The sets of bits specify locations of portions of the input vector where particular value of interest reside. The switch circuits output multiple values of the input vector, which include the particular value of interest. A second stage of switch circuits is controlled by logic circuit that detects values on the outputs of the first stage of switch circuits and outputs the values of interest. In some embodiments, the values of interest may be non-zero values of a sparse input vector, and the switch circuits may be multiplexers.

First claim

What is claimed is:

1. A circuit to compress data comprising:
a first plurality of switch circuits having inputs coupled to a plurality of values of an input vector, the first plurality of switch circuits further having control inputs coupled to bits of a bit mask to selectively couple multiple values of the plurality of values on one input of each of the first plurality of switch circuits to corresponding outputs of the first plurality of switch circuits;
a second plurality of switch circuits having inputs coupled to the multiple values on the outputs of the first plurality of switch circuits; and
a logic circuit having inputs coupled to the outputs of the first plurality of switch circuits and having outputs coupled to select inputs of the second plurality of switch circuits, the logic circuit detecting particular values on the outputs of the first plurality of switch circuits and configuring the second plurality of switch circuits to each output one of the particular values.

2. The circuit of claim 1 , wherein the plurality of values comprises zero values and non-zero values, and wherein in the particular values are zero values.

3. The circuit of claim 1 , wherein the bit mask comprises a plurality of subsets of bits, each subset of bits selecting one of the particular values of the plurality of values, wherein each subset of bits is coupled to a different one of the first plurality of switch circuits.

4. The circuit of claim 1 , wherein the inputs of the first plurality of switch circuits are coupled to two or more values of the input vector.

5. The circuit of claim 4 , wherein each input of the first plurality of switch circuits is coupled to two values of the input vector.

6. The circuit of claim 1 , wherein the bits of the bit mask couple a particular plurality of values to the output of each switch circuits based on a binary tree selection.

7. The circuit of claim 1 , wherein the inputs of each switch circuit of the first plurality of switch circuits are coupled to the plurality of values of the input vector, and wherein the select inputs of each switch circuit are coupled to a different portion of a total number of bits of a bit mask to couple a unique subset of plurality of values to an output of each of the first plurality of switch circuits.

8. The circuit of claim 1 , wherein the first plurality of switch circuits and the second plurality of switch circuits are multiplexers.

9. The circuit of claim 1 , wherein the input vector comprises two (2) to a power of N bits, wherein the bit mask comprises a plurality of N minus 1 length sets of bits.

10. The circuit of claim 1 , wherein the logic circuit compares bits coupled to the control inputs of at least two switch circuits of the first plurality of switch circuits and configures a first switch circuit of the second plurality of switch circuits to output a first particular value from a first set of multiple values and configures a second switch circuit of the second plurality of switch circuits to output a second particular value from the first set of multiple values.

11. The circuit of claim 1 , wherein the first plurality of switch circuits comprise a plurality of stages.

12. The circuit of claim 1 , wherein the second plurality of switch circuits comprise a plurality of stages.

13. A method of compressing data comprising:
receiving an input vector comprising a plurality of values on a plurality of inputs of a first plurality of switch circuits;
selectively coupling, based on a plurality of sets of bits, multiple values of the plurality of values on the inputs of the first plurality of switch circuits to corresponding outputs of the first plurality of switch circuits;
receiving the multiple values from the outputs of the first plurality of switch circuits on a plurality of inputs of a second plurality of switch circuits; and
selectively coupling a portion of the multiple values to outputs of the second plurality of switch circuits, wherein the selectively coupling is based on particular values of the multiple values.

14. The method of claim 13 , wherein each set of bits specifies a position of one of said particular values in the input vector.

15. The method of claim 13 , wherein the plurality of values comprises zero values and non-zero values, and wherein in the particular values are zero values.

16. The method of claim 13 , wherein the bit mask comprises a plurality of subsets of bits, each subset of bits selecting one of the particular values of the plurality of values, wherein each subset of bits is coupled to a different one of the first plurality of switch circuits.

17. The method of claim 13 , wherein the inputs of the first plurality of switch circuits are coupled to two or more values of the input vector.

18. The circuit of claim 17 , wherein each input of the first plurality of switch circuits is coupled to two values of the input vector.

19. The method of claim 13 , wherein the inputs of each switch circuit of the first plurality of switch circuits are coupled to the plurality of values of the input vector, and wherein select inputs of each switch circuit are coupled to a different portion of a total number of bits of a bit mask to couple a unique subset of plurality of values to an output of each of the first plurality of switch circuits.

20. A non-transitory machine-readable medium storing a hardware definition language (HDL) program executable by a computer, the program comprising sets of instructions for:
receiving an input vector comprising a plurality of values on a plurality of inputs of a first plurality of switch circuits;
selectively coupling, based on a plurality of sets of bits, multiple values of the plurality of values on the inputs of the first plurality of switch circuits to corresponding outputs of the first plurality of switch circuits;
receiving the multiple values from the outputs of the first plurality of switch circuits on a plurality of inputs of a second plurality of switch circuits; and
selectively coupling a portion of the multiple values to outputs of the second plurality of switch circuits, wherein the selectively coupling is based on particular values of the multiple values.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Shah Nishit
• More Ankit
• Heddes Mattheus C

Classifications

• H03M7/4093 Primary

  Variable length to variable length coding · CPC title

• H03M7/3066 Primary

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

• H03M7/405

  Tree adaptation · CPC title