# US 2002/0178195 A1 · Memory address generating apparatus and method

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

- Number: US 2002/0178195 A1
- Document ID: US20020178195A1
- Status: Published application
- Kind: A1
- Application number: 10/152,940
- Filed: 2002-05-22
- Published: 2002-11-28
- Earliest claimed: 2001-05-23
- Assignees: LG Electronics Inc.
- Inventors: Joo-Hyeon Ryu
- Web page: https://patentgrep.com/patent/US20020178195A1

## CPC

- G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A memory address generating method in which a memory bank index and an address control signal, that are required for a series of FFT processes in which a plurality of butterfly input samples are concurrently read from the same number of memory banks, a butterfly calculation is performed thereon by using the plurality of butterfly input samples, and the results are concurrently stored at the same position with the input samples, are calculated within a fixed small delay time by using a differential parity counter.

## Claims

### Claim 1

A memory address generating method in which a plurality of butterfly input samples are concurrently read from the same corresponding number of sample memory banks, a butterfly calculation is performed by using the plurality of butterfly input samples, and a memory bank index and an address control signal required for a series of FFT processes for storing the results at the same position as that of the input samples, are calculated within a fixed small delay time by using a differential parity counter.

### Claim 2 (depends on 1)

The method of claim 1, wherein the memory bank index is the same as a parity value of a data counter, and an address of the sample memory bank is calculated by a data count value.

### Claim 3 (depends on 1)

The method of claim 1, wherein, in the butterfly calculation, a plurality of input values are simultaneously received from each sample memory bank and calculated, and a resultant data is simultaneously stored in the sample memory bank in the same corresponding position.

### Claim 4 (depends on 3)

The method of claim 3, wherein the butterfly calculation is performed upon an input value from the sample memory bank and a coefficient.

### Claim 5 (depends on 1)

The method of claim 1, wherein a butterfly counter deforming unit calculates an address corresponding to each memory bank, so as to have the same sample memory bank index and address when a data is inputted or outputted at each stage.

### Claim 6 (depends on 1)

The method of claim 1, wherein the differential parity counter selects one of each specific bit of the data counter and a parity change value to output it as a parity change value, inverts a final output signal of the parity change value, XORs the inverted parity change value and a current parity value stored in a flip-flop and stores the resultant value as the next parity value in the flip-flop, thereby having a fixed small delay time irrespective of a size of an FFT.

### Claim 7 (depends on 5)

The method of claim 5, wherein the butterfly counter deforming unit XORs a value of the butterfly counter and a shift value of a pass shift register, so as to calculate an address.

### Claim 8 (depends on 1)

The method of claim 1, wherein the sample memory bank may be plural ones to concurrently read and write a plurality of input or output data, and generate a parity of a small delay time fixed by a data counter value for every clock.

### Claim 9

A memory address generating method comprising:
a data input step for receiving a time domain data for every clock cycle and concurrently storing it in a sample memory bank-0 and a sample memory bank-1;
a butterfly calculation step for reading two time domain data from the sample memory bank-0 and the sample memory bank-1 and performing a butterfly calculation thereon according to each stage together with a twiddle factor, and concurrently storing frequency domain data in each sample memory bank as two resultant data; and
a data output step for receiving the two frequency domain data and outputting it to an output terminal one by one for every clock cycle through a multiplexer.

### Claim 10 (depends on 9)

The method of claim 9, wherein, in the butterfly calculation step, the input address and the output address of the sample memory bank for the butterfly calculation are the same with each other, the pass shift register shifts once for each stage, and the butterfly counter sequentially increases a count value for every butterfly calculation.

### Claim 11 (depends on 9)

The method of claim 9, wherein, in the butterfly calculation step, input and output addresses of the sample memory bank-0 are the same with the butterfly counter at an arbitrary stage, and input and output addresses of the sample memory bank-1 are an XOR calculation result of the pass shift register and the butterfly counter.

### Claim 12 (depends on 9)

The method of claim 9, wherein, in the data input and output step, the bank index of the outputted data is the same with the parity value of the data counter, and the address of the sample memory bank is obtained from a data count value.

### Claim 13

A sample memory address generating apparatus comprising:
a sample memory bank-0 and a sample memory bank-1 in which input and output data at each stage of a butterfly calculation are stored at the same position or read therefrom; and
a sample memory address generator for generating a memory address of the sample memory bank.

### Claim 14 (depends on 13)

The apparatus of claim 13, further comprising:
a coefficient memory for storing a twiddle factor, coefficient of the butterfly calculation;
a coefficient memory address generator for generating an address of the coefficient memory;
a butterfly calculator for receiving the data from the sample memory bank and the coefficient from the coefficient memory, and performing a butterfly calculation on them;
a multiplexer for receiving the data outputted from the sample memory bank and a bank index from the memory address generator, and outputting an FFT calculation result; and
a controller for outputting a counter value to control an operation of the apparatus.

### Claim 15 (depends on 13)

The apparatus of claim 13, wherein the memory address generator comprises:
a differential parity counter for calculating a parity as a bank index of the sample memory; and
a butterfly counter deforming unit for calculating an address of the sample memory bank.

### Claim 16

A memory address generating apparatus comprising:
a sample memory bank-0 and a sample memory bank-1 for concurrently storing or reading an input data and an output data of a butterfly calculation operation;
a sample memory address generator for generating a parity and an address of the sample memory bank and outputting them;
a butterfly calculator for concurrently reading input data of the sample memory bank, performing a butterfly calculation on them, and outputting and storing the calculation result in the sample memory bank; and
a multiplexer for receiving the data outputted from the sample memory bank and a bank index from the sample memory address generator, and outputting an FFT calculation result.

### Claim 17 (depends on 16)

The apparatus of claim 16, further comprising:
a controller for generating a counter value to control an operation of the apparatus in a fast Fourier transforming operation.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein the controller comprises:
a data counter for increasing a data count (d6˜d0) in a positive direction from ‘0’ for every clock cycle;
a butterfly counter for increasing a butterfly count (b5˜b0) in a positive direction for every clock cycle; and
a pass shift register (p6˜p0) for performing a shift operation for every pass stage.

### Claim 19 (depends on 16)

The apparatus of claim 16, further comprising:
a coefficient memory for storing a twiddle factor, butterfly calculation coefficient; and
a coefficient memory address generator for generating an address of the coefficient memory.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein, in the butterfly calculation, input data are read from each sample memory bank to perform a calculation together with the twiddle factor, and the data are stored in the sample memory banks.

### Claim 21 (depends on 16)

The apparatus of claim 16, wherein the memory address generator includes: a differential parity counter for calculating a parity as a bank index having a fixed small delay time; and a butterfly counter deforming unit for calculating an address, so as to have the same memory bank index and address in inputting and outputting data at each stage.

### Claim 22 (depends on 21)

The apparatus of claim 21, wherein the differential parity counter comprises:
a multiplexer for calculating a parity change value for every clock cycle of a data counter;
a NOT gate for inverting an output signal of the multiplexer unit;
an AND gate unit for calculating a count of the data counter and outputting a signal to control the multiplexer unit;
a flip-flop for storing a current parity value (pr); and
an XOR gate for XORing the current parity value and a parity change value (g0) outputted from the NOT gate to calculate the next parity value (in_pr), and storing the next parity value (in_pr) in the flip-flop.

### Claim 23 (depends on 22)

The apparatus of claim 22, wherein the multiplexer unit comprises:
a multiplexer for selecting one of a specific one bit (d0) of the data counter and a parity change value (g1);
a multiplexer for selecting one of a specific one bit (d2) of the data counter and a parity change value (g2) and outputting it as the parity change value (g1); and
a multiplexer for selecting one of a specific bit (d4) of the data counter and a parity change value (g3=d6) and outputting it as the parity change value (g2).

### Claim 24 (depends on 22)

The apparatus of claim 22, wherein the AND gate unit comprises:
an AND gate for ANDing two specific bits (d0) (d1) of the data counter and outputting its result as a first control signal of the multiplexer unit;
an AND gate for ANDing two specific bits (d2) (d3) of the data counter and outputting its result as a selected control signal of the multiplexer unit: and
an AND gate for ANDing two specific bits (d4) (d5) of the data counter and outputting its result as a third control signal of the multiplexer unit.

### Claim 25 (depends on 21)

The apparatus of claim 21, wherein the butterfly counter deforming unit is constructed as an XOR gate for XORing a value of the butterfly counter and a shift value of the shift register to calculate an address.

### Claim 26 (depends on 21)

The apparatus of claim 21, wherein the butterfly counter deforming unit shifts the pass shift register for every pass stage.

### Claim 27 (depends on 16)

The apparatus of claim 16, wherein the sample memory bank includes a plurality of sample memory banks for concurrently reading and writing a plurality of input and output data.
