# US 2004/0083253 A1 · Method and apparatus for efficient matrix multiplication in a direct sequence CDMA system

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

- Number: US 2004/0083253 A1
- Document ID: US20040083253A1
- Status: Published application
- Kind: A1
- Application number: 10/357,124
- Filed: 2003-02-03
- Published: 2004-04-29
- Earliest claimed: 2002-10-29
- Assignees: Broadcom Corporation
- Inventors: Yung-Hsiang Lee
- Web page: https://patentgrep.com/patent/US20040083253A1

## CPC

- H04B 1/7093: Matched filter type
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- H04B 2001/70935: {using a bank of matched fileters, e.g. Fast Hadamard Transform}
- H04B: TRANSMISSION
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method are disclosed for efficiently performing multiplication of an input vector and an input matrix having a limited number of possible values for any element of the input matrix. Elements of the input matrix are grouped across a second dimension of the input matrix to form groups of matrix elements. All possible permutations of partial results for each of the groups of matrix elements are pre-computed. The partial results from each of the groups of matrix elements are assigned to each of a corresponding index of a first dimension of the input matrix to form a matrix of assigned partial results. The assigned partial results are summed along the first dimension of the matrix of assigned partial results to form a vector of full matrix multiplication results.

## Claims

### Claim 1

In a system performing multiplication of an input vector and an input matrix having a limited number of possible values for any element of said input matrix, a method to efficiently perform said multiplication comprising:
grouping elements of said input matrix across a second dimension of said input matrix to form groups of matrix elements;
pre-computing all possible permutations of partial results for each of said groups of matrix elements;
assigning said partial results from each of said groups of matrix elements to each of a corresponding index of a first dimension of said input matrix to form a matrix of assigned partial results; and
summing said assigned partial results along said first dimension of said matrix of assigned partial results to form a vector of full matrix multiplication results.

### Claim 2 (depends on 1)

The method of claim 1 wherein said pre-computing comprises performing at least one of addition, subtraction, and multiplication.

### Claim 3 (depends on 1)

The method of claim 1 wherein said matrix of assigned partial results is generated over time as corresponding elements of said input matrix are pipeline-processed to generate said partial results.

### Claim 4 (depends on 1)

The method of claim 1 wherein said summing is performed in a time-shared manner as assigned partial results become available for summing.

### Claim 5 (depends on 1)

The method of claim 1 wherein each element of said input matrix comprises a value of +1 or −1.

### Claim 6 (depends on 1)

The method of claim 1 wherein each element of said input vector comprises an uncoded symbol in a direct-sequence CDMA transmitter.

### Claim 7 (depends on 1)

The method of claim 1 wherein each element of said input vector comprises a coded symbol in a direct-sequence CDMA receiver.

### Claim 8 (depends on 1)

The method of claim 1 wherein each index of said first dimension of said input matrix corresponds to a direct-sequence code of said input matrix.

### Claim 9 (depends on 1)

The method of claim 1 wherein said input matrix comprises an inverse of a matrix of direct-sequence codes.

### Claim 10 (depends on 1)

The method of claim 1 wherein said grouping comprises performing an optimal grouping based on tradeoffs between performance, power, cost, and hardware for said system.

### Claim 11 (depends on 1)

The method of claim 1 wherein said first dimension corresponds to a row dimension of said input matrix and said matrix of partial results.

### Claim 12 (depends on 1)

The method of claim 1 wherein said second dimension corresponds to a column dimension of said input matrix and said matrix of partial results.

### Claim 13

In a direct-sequence CDMA system, apparatus to efficiently perform matrix multiplication, said apparatus comprising:
a pre-computation module that generates a matrix of partial results from an input matrix and an input vector by, in part, grouping elements along a second dimension of said input matrix; and
a post-computation module that sums along a first dimension of said matrix of partial results in a time-shared manner to form a vector of full matrix multiplication results as partial results in said matrix of partial results become available from said pre-computation module.

### Claim 14 (depends on 13)

The apparatus of claim 13 further comprising a time-shared accumulator module, shared between said pre-computation module and said post-computation module, that accumulates said partial results and said full matrix multiplication results.

### Claim 15 (depends on 13)

The apparatus of claim 13 further comprising an analog-to-digital converter that digitizes said input vector before use by said pre-computation module.

### Claim 16 (depends on 13)

The apparatus of claim 13 further comprising an ingress/channel cancellation filter that filters said input vector before use by said pre-computation module.

### Claim 17 (depends on 13)

The apparatus of claim 13 further comprising a vector register that stores said vector of full matrix multiplication results.

### Claim 18 (depends on 13)

The apparatus of claim 13 wherein said input matrix comprises a matrix of direct-sequence codes.

### Claim 19 (depends on 13)

The apparatus of claim 13 wherein said input matrix comprises an inverse matrix of direct-sequence codes.

### Claim 20 (depends on 13)

The apparatus of claim 13 wherein said input vector comprises a vector of uncoded symbols.

### Claim 21 (depends on 13)

The apparatus of claim 13 wherein said input vector comprises a vector of coded symbols.

### Claim 22 (depends on 13)

The apparatus of claim 13 wherein each element of said input matrix comprises a value of +1 or −1.

### Claim 23 (depends on 13)

The apparatus of claim 13 wherein said grouping elements comprises performing an optimal grouping based on tradeoffs between performance, power, cost, and hardware for said CDMA system.

### Claim 24 (depends on 13)

The apparatus of claim 13 wherein said first dimension corresponds to a row dimension of said input matrix and said matrix of partial results.

### Claim 25 (depends on 13)

The method of claim 13 wherein said second dimension corresponds to a column dimension of said input matrix and said matrix of partial results.
