Efficient encoding methods
A method of encoding data values comprises mapping each of a plurality of input values to one of a pre-defined set of codes based on a probability distribution of the input values. In various examples an input value may be mapped to a code having the same bit-length as the input value and in other examples, the code may be longer than the input value. In various examples, the input values may be grouped into data words and may additionally comprise one or more padding bits.
1 . A method of reducing power consumption of read/write operations of a processor by encoding data values, the method comprising:
receiving at a computing entity a plurality of input data values, the input data values representing data that is to be processed by said processor;
mapping, by said computing entity, each input data value to one of a pre-defined set of codes based on a probability distribution of the input data values and a characteristic of the code of the pre-defined set of codes, wherein the characteristic of the code of the pre-defined set of codes comprises a number of bit flips within the code of the pre-defined set of codes;
outputting the codes corresponding to the received input data values; and
transmitting the outputted codes, optionally over a data bus, to a memory to be stored therein for processing by said processor.
2 . The method according to claim 1 , wherein, compared to an input value having a relatively low probability according to the probability distribution, an input value having a relatively high probability according to the probability distribution is mapped to a code of the pre-defined set of codes which has closer to a target number of bit flips within the code of the pre-defined set of codes.
3 . The method according to claim 1 , wherein mapping each input data value to one of a pre-defined set of codes based on a probability distribution of the input data values comprises, for an input data value:
determining a probability index for the input data value based on the probability distribution of the input data values; and
mapping the probability index to one of the pre-defined set of codes.
4 . The method according to claim 3 , wherein determining a probability index for the input data value based on the probability distribution of the input data values comprises one of:
determining a probability index for the input data value using a look-up table;
sign remapping the input data value;
determining a probability index for the input data value based on a length of the input data value or of a tail portion of the input data value;
determining a probability index for the input data value using a probability distribution builder, wherein the probability distribution builder accumulates frequencies for each possible value over a pre-defined number of input data values;
determining a probability index for the input data value using a probability distribution builder, wherein the probability distribution builder dynamically accumulates frequencies for each possible value and is updated for each input data value or group of input data values.
5 . The method of claim 1 , wherein each input data value is mapped to a code that comprises either: (i) the same number of bits as the input data value, or (ii) more bits than the input data value.
6 . The method according to claim 3 , wherein mapping the probability index to one of the pre-defined set of codes comprises:
mapping the probability index to one of the pre-defined set of codes using a look-up table.
7 . The method according to claim 3 , wherein mapping the probability index to one of the pre-defined set of codes comprises:
identifying a subset of the codes based on the probability index; and
identifying one of the subsets of the codes.
8 . The method according to claim 7 , identifying the subset of the codes based on the probability index comprises:
using an iterative method to identify the subset, each iteration comprising comparing the probability index to a binomial coefficient; and/or
identifying the subset using a look-up table.
9 . The method according to claim 7 , wherein identifying one of the subsets of the codes comprises identifying one of the subsets of the codes using a look-up table.
10 . The method according to claim 2 , further comprising, prior to determining a probability index for the input data value based on the probability distribution of the input data values:
decorrelating the input data values;
and wherein the probability indices are determined for decorrelated input data values based on the probability distribution of the decorrelated input data values.
11 . The method according to claim 1 , further comprising, prior to outputting the codes, for each code of the pre-defined set of codes:
modifying the code of the pre-defined set of codes by combining by, for each bit in the code of the pre-defined set of codes in turn, selecting a bit located B-bits to the left of the bit and combining the bit with the selected bit in an XOR function to generate a modified bit, wherein B is an integer.
12 . The method according to claim 11 , wherein:
B=1; or
B is a bit width of an external bus over which the codes are to be transmitted; or
B is a highest common factor of the bit widths of each of a plurality of external buses over which the codes are to be transmitted.
13 . The method according to claim 1 , wherein receiving the plurality of input data values comprises receiving a plurality of input words, each input word comprising one or more input data values and one or more padding bits and wherein outputting the codes corresponding to the received input data values comprises outputting a plurality of output words, each output word corresponding to an input word and comprising the codes corresponding to the one or more input data values in the input word.
14 . The method according to claim 13 , wherein at least one input data value in each input word is mapped to a code comprising more bits than the input data value.
15 . The method according to claim 1 , wherein:
the probability distribution of the input data values is non-uniform; or
the probability distribution of the input data values is uniform and wherein each input data value is mapped to a code comprising more bits than the input data value.
16 . A computing entity comprising an encoding hardware block reducing power consumption of read/write operations of a processor, the encoding hardware block comprising:
an input configured to receive a plurality of input data values, the input data values representing data that is to be processed by at least one processor;
mapping hardware logic arranged to map each input data value to one of a pre-defined set of codes based on a probability distribution of the input data values and a characteristic of the code of the pre-defined set of codes, wherein the characteristic of the code of the pre-defined set of codes comprises a number of bit flips within the code of the pre-defined set of codes; and
an output for outputting the codes corresponding to the received input data values and transmitting the outputted codes, optionally over a data bus, to a memory to be stored therein for processing by said processor.
17 . A method of reducing power consumption of read/write operations of a processor, comprising:
receiving at a computing entity a plurality of input codes, the input codes representing data that is to be processed by said processor;
mapping, by said computing entity, each input code to one of a pre-defined set of previously decoded values based on a probability distribution of the decoded values and a characteristic of the code of the pre-defined set of codes, wherein the characteristic of the code of the pre-defined set of codes comprises a number of bit flips within the code of the pre-defined set of codes;
outputting the decoded values corresponding to the received input codes; and
transmitting the decoded values, optionally over a data bus, to a memory to be stored therein for processing by said processor.
18 . The method according to claim 17 , wherein mapping each input code to one of a pre-defined set of previously decoded values based on a probability distribution of the decoded values comprises, for an input code:
mapping the input code to a probability index; and
mapping the probability index to one of the pre-defined set of previously decoded values based on the probability distribution of the decoded values.