# US 6,732,130 B2 · Fast hadamard transform device

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

- Number: US 6,732,130 B2
- Document ID: US6732130B2
- Status: Granted
- Kind: B2
- Application number: 09/745,649
- Filed: 2000-12-22
- Published: 2001-07-05
- Granted: 2004-05-04
- Earliest claimed: 1999-12-24
- Assignees: NEC Corporation
- Inventors: Takashi Shoji
- Web page: https://patentgrep.com/patent/US6732130B2

## CPC

- H04B 1/7093: Matched filter type
- H04B 2001/70935: {using a bank of matched fileters, e.g. Fast Hadamard Transform}
- H04B: TRANSMISSION

## Abstract

A fast Hadamard transform device is provided which prevent from increasing of circuit scale and shorten a developing TAT even if the number of bits to be operated. The device includes n of shift register units and n/2 of butterfly computation units. Input data are entered to the shift register units in response to a signal and data stored in the shift register units are supplied as quantized data by providing a signal for each “log2n*(p+log2n)” clocks.

## Claims

### Claim 1

A fast Hadamard transform device which transforms n elements of input data each of which is composed of p bits, comprising:
n of shift register units each of which inputs a corresponding element of the input data at a predetermined input timing and outputs the bits in the input data serially; and
n/2 of butterfly computation units each of which receives a bit from each two of the n shift register units and performs addition and subtraction on the two bits to supply each operation result to a determined shift register unit.

### Claim 2 (depends on 1)

The fast Hadamard transform device of claim 1, wherein each of the shift register units operates as output latches holding (p+log2n) signals from one of the butterfly computation units at a predetermined output timing, and operates as (p+log2n) steps of shift registers in response to entering the input data and signals from one of the butterfly computation units at an other timing.

### Claim 3 (depends on 2)

The fast Hadamard transform device of claim 2, wherein each of the butterfly computation units includes:
an adder which performs addition on two bits which are shifted from different shift register units and a carry bit which is stored in the former addition; and
a subtractor which performs subtraction on two bits which are shifted from the different shift register units and a borrow bit which is stored in the former subtraction.

### Claim 4 (depends on 3)

The fast Hadamard transform device of claim 3, wherein each of the carry bit and the borrow bit is stored in a delay circuit which is initialized every (log2n*(p+log2n)) shift timings.

### Claim 5 (depends on 3)

The fast Hadamard transform device of claim 3, wherein serial output of the shift register unit corresponding to the 2q−1-th (1≦q≦4, q is a natural number) order is connected to an input to the adder of the q-th butterfly computation unit, serial output of the shift register unit corresponding to the 2q-th order is connected to an input to the subtractor of the q-th butterfly computation unit, an output from the adder of the r-th (1≦r≦4, r is a natural number) butterfly computation unit is connected to the serial input of the r-th shift register unit, and an output from the subtractor of the r-th butterfly computation unit is connected to the serial input of the r+4-th shift register unit.
