# US 2003/0217084 A1 · Method of generating a cycle-efficient bit-reverse index array for a wireless communication system

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

- Number: US 2003/0217084 A1
- Document ID: US20030217084A1
- Status: Published application
- Kind: A1
- Application number: 10/438,241
- Filed: 2003-05-14
- Published: 2003-11-20
- Earliest claimed: 2002-05-14
- Assignees: Texas Instruments Incorporated
- Inventors: David P. Magee
- Web page: https://patentgrep.com/patent/US20030217084A1

## CPC

- G06F 7/768: {Data position reversal, e.g. bit reversal, byte swapping}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An efficient method of generating a bit-reverse index array in real time without performing any bit manipulation for a wireless communication system.

## Claims

### Claim 1

In a data processing device including a central processing unit and a memory, a method of generating a bit-reverse index array for a wireless communication system, the method comprising the steps of:
(a) initializing a first value of an index array, stored in the memory, to 0;
using the central processing unit:
(b) multiplying the initialized first value by the number 2 to generate a first portion of the index array;
(c) adding the number 1 to the first portion of the index array to generate a second portion of the index array, wherein the first portion and the second portion comprise a new set of numbers;
(d) multiplying each number in the new set of numbers by the number 2 to generate a new first portion of the index array, wherein the new first portion of the index array comprises a new set of numbers;
(e) adding the number 1 to each number in the new first portion of the index array to generate a new second portion of the index array, wherein the new first portion and the new second portion comprises a new set of numbers; and
(f) repeating steps (d) and (e) until the index array grows to a bit-reverse index array having a desired length.

### Claim 2 (depends on 1)

The method according to claim 1 wherein the step of repeating steps (d) and (e) until the index array grows to a bit-reverse index array having a desired length comprises performing a combined total of log2(N) steps, where N is the length of the desired bit-reverse index array.

### Claim 3 (depends on 1)

The method according to claim 1 wherein each multiplication for each step comprises solely performing a left shift operation.

### Claim 4 (depends on 1)

The method according to claim 1 wherein each addition for each step comprises solely performing an increment operation.

### Claim 5 (depends on 1)

The method according to claim 1 wherein the initializing, multiplication and addition steps are achieved without bit manipulation of any individual index value.

### Claim 6 (depends on 1)

The method according to claim 1 wherein the initializing, multiplication and addition steps are achieved without evaluating any binary representations of index values.

### Claim 7

In a data processing device that includes a central processing unit and a memory, a method of generating a bit-reverse index array comprising the steps of:
(a) initializing a first value of an index array stored in the memory to 0 to generate a first portion of the index array;
using the central processing unit:
(b) adding the number 1 to the first portion of the index array to generate a second portion of the index array, wherein the first portion and the second portion comprise a new set of numbers;
(c) multiplying each number in the new set of numbers by the number 2 to generate a new first portion of the index array, wherein the new first portion of the index array comprises a new set of numbers;
(d) adding the number 1 to each number in the new first portion of the index array to generate a new second portion of the index array, wherein the new first portion and the new second portion comprises a new set of numbers; and
(e) repeating steps (c) and (d) until the index array grows to a bit-reverse index array having a desired length.

### Claim 8

In a data processing device having a memory and a central processing unit, a method of generating a bit reversed index array of n-bit binary values, the method comprising the steps of:
(a) initializing a first portion of the index array stored in the memory;
using the central processing unit:
(b) computing each value in the first portion of the index array by multiplying each said value by a first predetermined amount;
(c) updating each value in the first portion of the index array;
(d) computing each value in a second portion of the index array by adding a second predetermined amount to a corresponding one of the first portion of the index array;
(e) updating each value in the second portion of the index array;
(f) re-defining the first portion of the index array to include the second portion of the index array; and
(g) repeating steps (b) through (f) until the re-defined first portion of the index array is of a desired length, wherein the index to each element in the index array being the bit reverse of the value stored in that element of the index array.

### Claim 9 (depends on 8)

The method of claim 8 wherein the desired length of the index array is 2n.

### Claim 10 (depends on 8)

The method of claim 8 wherein the first portion of the index array is initialized to zero.

### Claim 11 (depends on 8)

The method of claim 8 wherein the first predetermined value is 2 and the second predetermined amount is 1.

### Claim 12 (depends on 8)

The method of claim 8 wherein the first portion of the index array and the second portion of the index array are the same length.

### Claim 13 (depends on 1)

The method of claim 1 wherein the first portion of the index array is a first set of memory locations in a digital signal processing device and the second portion of the index array is a second set of memory locations in the digital signal processing device.

### Claim 14 (depends on 13)

The method of claim 13 wherein the step computing each value in the first portion of the index array by multiplying said each value by a predetermined amount includes the step of left shifting the value in the said memory location.

### Claim 15 (depends on 14)

The method of claim 14 wherein the step of computing each value in the second portion of the index array by adding the second predetermined amount to a corresponding value in the first portion of the index array includes the step of computing each value in the second portion of the index array by incrementing a corresponding value in the first portion of the index array.

### Claim 16 (depends on 15)

The method of claim 15 wherein the step of updating the first portion of the index array and the step of computing the second portion of the index array are performed in a single clock cycle of the digital signal processing device.
