Partially and fully parallel normaliser

Patent metadata

Field	Value
Publication number	US-9703525-B2
Application number	US-201414576859-A
Country	US
Kind code	B2
Filing date	Dec 19, 2014
Priority date	Dec 20, 2013
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

Hardware logic arranged to normalize (or renormalize) 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 renormalization block which completes the remainder of the left shifting operation independently of any further input from the leading zero counter.

First claim

The invention claimed is:

1. An apparatus comprising hardware logic arranged to normalise an input n-bit binary number, the hardware logic comprising:
a leading zero counter arranged to compute a number of leading zeros in the n-bit number; and
left shifting logic arranged to perform left shifting of the n-bit number,
wherein at least a portion of the left shifting is performed in parallel with the computing of the number of leading zeros and without input from the leading zero counter.

2. An apparatus according to claim 1 , wherein the left shifting logic comprises a normaliser block arranged to operate independently of the leading zero counter.

3. An apparatus according to claim 2 , wherein the normaliser 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,
j is a bit index associated with each of the n-bits in the input number,
a j is the j th bit in the input number, and
i is a bit index associated with each bit r i output by the normaliser block.

4. An apparatus according to claim 3 , wherein the normaliser 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 .

5. An apparatus according to claim 1 , wherein the left shifting logic comprises:
a left shifter arranged to receive a subset of the bits, starting from a most significant bit, generated by the leading zero counter and to left shift the n-bit number based on the received bits; and
a normaliser block arranged to receive an output from the left shifter and to generate an output comprising a normalised version of the n-bit number.

6. An apparatus according to claim 5 , wherein the normaliser 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,
j is a bit index associated with each of the n-bits in the input number,
a′ j is the j th bit in the number output by the left shifter, and
i is a bit index associated with each bit r i output by the renormaliser block.

7. An apparatus according to claim 6 , wherein the normaliser 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 leading zero counter comprises h bits, and
B j:t = a j · a j−1 . . . a t+1 · a t .

8. A method of normalising an input n-bit binary number, the method comprising:
computing, by hardware logic a number of leading zeros in the n-bit number in a leading zero counter; and
left shifting the n-bit number in left shifting hardware logic, wherein at least a portion of the left shifting is performed in parallel with the computing of the number of leading zeros and without input from the number of leading zeros computation.

9. A non-transitory computer readable storage medium having stored thereon computer executable program code that when executed causes at least one processor to compute a number of leading zeros in the n-bit number in a leading zero counter; and
left shift the n-bit number, wherein at least a portion of the left shifting is performed in parallel with the computing of the number of leading zeros and without input from the number of leading zeros computation.

10. A non-transitory computer readable storage medium having stored thereon computer executable program code that, when executed at a computer system for generating a representation of a digital circuit from definitions of circuit elements and data defining rules for combining those circuit elements, cause the computer system to generate hardware logic arranged to normalise an input n-bit binary number, the hardware logic comprising:
a leading zero counter arranged to compute a number of leading zeros in the n-bit number; and
normalisation logic arranged to perform left shifting of the n-bit number, wherein at least a portion of the left shifting is performed in parallel with the computing of the number of leading zeros and without input from the leading zero counter.

Assignees

• Imagination Tech Ltd

Inventors

• Drane Theo Alan

Classifications

• G06F5/01 Primary

  for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)} · CPC title

• G06F7/74

  Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders {(with shifting G06F5/01)} · CPC title

• G06F2205/003

  Reformatting, i.e. changing the format of data representation · CPC title