# US 10,771,090 B2 · Data processing unit having hardware-based range encoding and decoding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,771,090 B2
- Document ID: US10771090B2
- Status: Granted
- Kind: B2
- Application number: 16/711,715
- Filed: 2019-12-12
- Published: 2020-05-07
- Granted: 2020-09-08
- Earliest claimed: 2018-11-01
- Assignees: Fungible, Inc.
- Applicants: Fungible, Inc.
- Inventors: Rajan Goyal; Satyanarayana Lakshmipathi Billa; Gurumani Senthil Nayakam
- Web page: https://patentgrep.com/patent/US10771090B2

## CPC

- H03M 7/4006: {Conversion to or from arithmetic code}
- G06F 12/0207: {with multidimensional access, e.g. row/column, matrix}
- H03M 7/4093: {Variable length to variable length coding}
- H03M 7/6011: {Encoder aspects}
- H03M 7/6029: {Pipelining}
- H03M 13/45: Soft decoding, i.e. using symbol reliability information (H03M13/41 takes precedence)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A highly programmable data processing unit includes multiple processing units for processing streams of information, such as network packets or storage packets. The data processing unit includes one or more specialized hardware accelerators configured to perform acceleration for various data-processing functions. The data processing unit is configured to retrieve speculative probability values for range coding a plurality of bits with a single read instruction to an on-chip memory that stores a table of probability values. The data processing unit is configured to store state information used for context-coding packets of a data stream so that the state information is available after switching between data streams.

## Claims

### Claim 1

A method of context-based coding, the method comprising:
determining, by a range coder implemented in circuitry of a device, a first context value for a first context for a plurality of bits of a symbol to be coded, wherein the first context value for the first context is same for the plurality of bits;
retrieving, by the range coder, speculative probability values associated with the first context value for the first context from a table of probability values;
for one or more bits of the plurality of bits of the symbol, determining, by the range coder, respective second context values for a second context;
for the one or more bits of the plurality of bits of the symbol, determining, by the range coder, respective probability values from the retrieved speculative probability values based on at least the respective second context values for the second context; and
range coding, by the range coder, the one or more bits of the plurality of bits of the symbol based on the respective determined probability values.

### Claim 2 (depends on 1)

The method of claim 1, wherein a second context value for a second context for a first bit of the one or more bits is different than a second context value for a second context for a second bit of the one or more bits.

### Claim 3 (depends on 1)

The method of claim 1, wherein retrieving comprises retrieving, in response to a single read instruction issued to the on-chip memory.

### Claim 4 (depends on 1)

The method of claim 1, wherein retrieving the probability values comprises retrieving the probability values from an on-chip memory storing the table of probability values arranged in contiguous memory locations within the on-chip memory.

### Claim 5 (depends on 4)

The method of claim 4, wherein the table of probability values is arranged as a two-dimensional structure of memory locations, wherein retrieving the speculative probability values comprises:
determining a row or column in the two-dimensional structure of memory locations indexed by the first context value of the first context; and
retrieving all of the speculative probability values stored in the row or column indexed by the first context value of the first context.

### Claim 6 (depends on 1)

The method of claim 1, wherein the symbol to be coded comprises one of:
a literal of a byte string; or
a length, distance pair indicating a distance value to a previous occurrence of a matching byte string and a length value of the match.

### Claim 7 (depends on 1)

The method of claim 1, wherein the symbol to be coded comprises a length, distance pair indicating a distance value to a previous occurrence of a matching byte string and a length value of the match, wherein the first context value of the context comprises a context value for a state context based on a classification of symbols coded prior to the symbol to be coded, and the second context value comprises an offset value based on a history position.

### Claim 8 (depends on 1)

The method of claim 1, wherein the symbol to be coded comprises a literal of a byte string, and wherein the first context value of the first context comprises four most significant bits of a previous uncompressed byte, and the second context value of the second context comprises an offset value based on a history position.

### Claim 9 (depends on 1)

The method of claim 1, wherein retrieving speculative probability values comprises retrieving all potential probability values for all of the bits in the one or more bits.

### Claim 10 (depends on 1)

The method of claim 1, wherein the symbol comprises a current symbol, the method further comprising:
determining one or more indices in the table of probability values for bits of a next symbol while range coding the current symbol; and
retrieving speculative probability values for the next symbol based on the determination while range coding the current symbol.

### Claim 11

A device for context-coding, the device comprising:
memory configured to store a table of probability values; and
a range coder implemented in circuitry, wherein the range coder is configured to:
retrieve speculative probability values associated with a first context value for a first context for a plurality of bits of a symbol to be coded from the table of probability values stored in the memory, wherein the first context value for the first context is same for the plurality of bits;
for one or more bits of the plurality of bits of the symbol, determine respective second context values for a second context;
for the one or more bits of the plurality of bits of the symbol, determine respective probability values from the retrieved speculative probability values based on at least the respective second context values for the second context; and
range code the one or more bits of the plurality of bits of the symbol based on the respective determined probability values.

### Claim 12 (depends on 11)

The device of claim 11, wherein a second context value for a second context for a first bit of the one or more bits is different than a second context value for a second context for a second bit of the one or more bits.

### Claim 13 (depends on 11)

The device of claim 11, wherein to retrieve, the range coder is configured to retrieve, in response to a single read instruction issued to the memory, the speculative probability values.

### Claim 14 (depends on 11)

The device of claim 11, wherein to retrieve the probability values, the range coder is configured to retrieve the probability values from the memory storing the table of probability values arranged in contiguous memory locations within the memory.

### Claim 15 (depends on 14)

The device of claim 14, wherein the table of probability values is arranged as a two-dimensional structure of memory locations, wherein to retrieve the speculative probability values, the range coder is configured to:
determine a row or column in the two-dimensional structure of memory locations indexed by the first context value of the first context; and
retrieve all of the speculative probability values stored in the row or column indexed by the first context value of the first context.

### Claim 16 (depends on 11)

The device of claim 11, wherein the symbol to be coded comprises one of:
a literal of a byte string; or
a length, distance pair indicating a distance value to a previous occurrence of a matching byte string and a length value of the match.

### Claim 17 (depends on 11)

The device of claim 11, wherein the symbol to be coded comprises a length, distance pair indicating a distance value to a previous occurrence of a matching byte string and a length value of the match, wherein the first context value of the context comprises a context value for a state context based on a classification of symbols coded prior to the symbol to be coded, and the second context value comprises an offset value based on a history position.

### Claim 18 (depends on 11)

The device of claim 11, wherein the symbol to be coded comprises a literal of a byte string, and wherein the first context value of the first context comprises four most significant bits of a previous uncompressed byte, and the second context value of the second context comprises an offset value based on a history position.

### Claim 19 (depends on 11)

The device of claim 11, wherein to retrieve speculative probability values, the range coder is configured to retrieve all potential probability values for all of the bits in the one or more bits.

### Claim 20 (depends on 11)

The device of claim 11, wherein the symbol comprises a current symbol, and wherein the range coder is configured to:
determine one or more indices in the table of probability values for bits of a next symbol while range coding the current symbol; and
retrieve speculative probability values for the next symbol based on the determination while range coding the current symbol.

### Claim 21

A device for context-coding, the device comprising:
a range coder implemented in circuitry, wherein the range coder is configured to:
retrieve speculative probability values associated with a first context value for a first context for a plurality of bits of a symbol to be coded; and
range code the one or more bits of the plurality of bits of the symbol based on probability values determined from the retrieved speculative probability values and respective second context values for a second context.

### Claim 22 (depends on 21)

The device of claim 21, wherein to retrieve, the range coder is configured to retrieve, in response to a single read instruction issued to the memory, the speculative probability values.

### Claim 23 (depends on 21)

The device of claim 21, wherein the device further comprises a memory configured to store a table of probability values arranged as a two-dimensional structure of memory locations, wherein to retrieve the speculative probability values, the range coder is configured to:
determine a row or column in the two-dimensional structure of memory locations indexed by the first context value of the first context; and
retrieve all of the speculative probability values stored in the row or column indexed by the first context value of the first context.

### Claim 24 (depends on 21)

The device of claim 21, wherein the symbol to be coded comprises one of:
a literal of a byte string; or
a length, distance pair indicating a distance value to a previous occurrence of a matching byte string and a length value of the match.

### Claim 25 (depends on 21)

The device of claim 21, wherein the symbol to be coded comprises a length, distance pair indicating a distance value to a previous occurrence of a matching byte string and a length value of the match, wherein the first context value of the context comprises a context value for a state context based on a classification of symbols coded prior to the symbol to be coded, and the second context value comprises an offset value based on a history position.

### Claim 26 (depends on 21)

The device of claim 21, wherein the symbol to be coded comprises a literal of a byte string, and wherein the first context value of the first context comprises four most significant bits of a previous uncompressed byte, and the second context value of the second context comprises an offset value based on a history position.