Partially and fully parallel normaliser
Hardware logic arranged to normalise (or renormalise) an n-bit input number is described in which at least a proportion of a left shifting operation is performed in parallel with a leading zero count operation. In various embodiments the left shifting and the leading zero count are performed independently. In various other embodiments, a subset of the bits output by a leading zero counter are input to a left shifter and the output from the left shifter is input to a renormalisation block which completes the remainder of the left shifting operation independently of any further input from the leading zero counter.
1. Hardware logic arranged to normalize or renormalize a binary number, the hardware logic comprising:
a zero counter arranged to count leading or trailing zeros in the binary number; and
a shifter arranged to shift the binary number;
wherein at least a portion of the shift is performed in parallel with the count.
2. Hardware logic according to claim 1 , wherein all of the shift is performed in parallel with the count.
3. Hardware logic according to claim 1 , wherein the shifter comprises a normalizer block arranged to operate independently of the zero counter.
4. Hardware logic according to claim 3 , wherein the normalizer block comprises hardware logic arranged to combine pairs of bits in the binary number according to:
r i j:j =a j .a j−n+1+i
where:
. represents an AND logic function,
n is a number of bits in the binary number,
j is a bit index associated with each of the n-bits in the binary number,
a j is the j th bit in the binary number, and
i is a bit index associated with each bit r i output by the normalizer block.
5. Hardware logic according to claim 4 , wherein the normalizer block further comprises hardware logic arranged to combine values r i j:j in the form of a tree of logic elements to compute output bits r i n−1:0 based on at least one of:
r i j:k =r i j:t +B j:t r i t−1:k and
r i j:k =( r i j:t +B j:t )( r i j:t +r i t−1:k )
where:
+ represents an OR logic function,
t and k are natural numbers, and
B j:t = a j . a j−1 . . . a t+1 . a t .
6. Hardware logic according to claim 1 , wherein the shifter is arranged to receive a subset of the bits, starting from a most significant bit, generated by the zero counter and to shift the binary number based on the received bits.
7. Hardware logic according to claim 6 , further comprising:
a normalizer block arranged to receive an output from the shifter and to generate an output comprising a normalised or renormalized version of the binary number.
8. Hardware logic according to claim 7 , wherein the normalizer block comprises hardware logic arranged to combine pairs of input bits according to:
r i j:j =a′ j .a′ j−n+1+i
where:
. represents an AND logic function,
n is a number of bits in the binary number,
j is a bit index associated with each of the n-bits in the binary number,
a′ j is the j th bit in the number output by the shifter, and
i is a bit index associated with each bit r output by the normalizer block.
9. Hardware logic according to claim 8 , wherein the normalizer block further comprises hardware logic arranged to combine values r i j:j in the form of a tree of logic elements to compute output bits r i n−1:n+1−2 α−h based on at least one of:
r i j:k =r i j:t +B j:t r i t−1:k and
r i j:k =( r i j:t +B j:t )( r i j:t +r i t−1:k )
where:
+ represents an OR logic function,
t and k are natural numbers,
α=└ log 2 n┘+1,
the subset of bits received from the zero counter comprises h bits, and
B j:t = a j . a j−1 . . . a t+1 . a t .
10. A method of normalizing or renormalizing a binary number by using hardware logic having a counter and a shifter, the method comprising:
counting, with the counter of the hardware logic, leading or trailing zeros in the binary number; and
shifting, with the shifter of the hardware logic, the binary number, and wherein at least a portion of the shifting is performed in parallel with the counting.
11. A method according to claim 10 , wherein all of the shifting is performed in parallel with the counting.
12. A non-transitory computer readable storage medium having stored thereon computer executable program code that when executed causes at least one processor comprising hardware logic having a counter and a shifter to
count, with the counter of the hardware logic, leading or trailing zeros in a binary number; and
shift, with the shifter of the hardware logic, the binary number, wherein at least a portion of the shift is performed in parallel with the count.
13. A non-transitory computer readable storage medium according to claim 12 , wherein all of the shift is performed in parallel with the count.