Multiple-access code generation

• US 20060239371A1
• Filed: 04/22/2005
• Published: 10/26/2006
• Est. Priority Date: 04/22/2005
• Status: Active Grant

• Current Assignee: Kansas State University Research Foundation
• Original Assignee: Kansas State University Research Foundation
• Inventors: Natarajan, Balasubramaniam, Dyer, Justin S.
• Granted Patent: US 7,587,660 B2
• Time in Patent Office: Days
• US Class Current: 375/265
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H04J 13/10 Code generation
• CPC Class Codes: H04L 5/026 using code division

Abstract

Multiple-access codes are generated using an asymptotically optimal decoding algorithm, such as the Viterbi algorithm. A trellis may be constructed using a number of desired users, at least one code length, and a number of code-chip parameters. A fitness function is derived from a mathematical relationship between the multiple-access codes, and may include some measure of correlation of the codes. The multiple-access codes correspond to paths having optimal path metrics derived from the fitness function. Multiple iterations through the trellis may be performed to refine a selection of multiple-access codes.

Claims

1. A method for generating at least one multiple-access code of a plurality of multiple-access codes, comprising;

providing for constructing a trellis based on;

a number of desired users,

at least one code length, and

a number of code-chip parameters, and

providing for forming at least one path through the trellis based on at least one fitness function derived from a mathematical relationship between the plurality of multiple-access codes, the path providing code-chip values of the at least one multiple-access code.

2. The method recited in claim 1, wherein providing for constructing the trellis includes providing for a code set ordered as a by-element variant topology or a by-user variant topology.

3. The method recited in claim 1, further comprising providing for an approximation to the at least one fitness function by employing only a portion of a total K×

N code-set matrix.

4. The method recited in claim 1, wherein the code-chip parameters include at least one of a set comprising phases and amplitudes.

5. The method recited in claim 1, wherein providing for forming at least one path through the trellis includes providing for a deterministic decision rule.

6. The method recited in claim 1, wherein the fitness function comprises at least one of an average mean-square aperiodic cross correlation, a maximum-square aperiodic cross-correlation, a spectral correlation function, an aperiodic autocorrelation configured for reducing peak-to-average-power ratio, and a Fourier transform of an aperiodic autocorrelation.

7. A digital computer system configured to perform the method recited in claim 1.

8. A computer program residing on a computer-readable medium, wherein the computer program is configured to perform the method recited in claim 1.

9. A method for generating at least one multiple-access code of a plurality of multiple-access codes, comprising;

providing for constructing a trellis having;

a plurality K×

N of state transition points,

each of the K×

N state transition points including L nodes, wherein

K is a number of desired users,

N is a code length, and

L is a number of a plurality of code-chip parameters, and

providing for constructing a fitness function that is computable for each of the plurality of state transition points, and

providing for employing the fitness function in an asymptotically optimal decoding algorithm configured to operate with the trellis for generating the at least one multiple-access code.

10. The method recited in claim 9, wherein providing for constructing the trellis includes providing for a code set ordered as a by-element variant topology or a by-user variant topology.

11. The method recited in claim 9, wherein providing for constructing the fitness function further comprises providing for an approximation to the fitness function by employing only a portion of a total K×

N code-set matrix.

12. The method recited in claim 9, wherein the plurality of code-chip parameters includes at least one of a set of code-chip parameters comprising, a plurality of phases uniformly distributed in a phase space, a plurality of non-uniformly distributed phases, and a plurality of amplitudes.

13. The method recited in claim 9, wherein providing for constructing the fitness function includes providing for constructing at least one of an average mean-square aperiodic cross-correlation function for a resulting code set, a maximum-square aperiodic cross-correlation for a resulting code set, a spectral correlation function, an aperiodic autocorrelation configured for reducing peak-to-average-power ratio, or a Fourier transform of an aperiodic autocorrelation.

14. The method recited in claim 9, wherein providing for constructing the trellis includes employing a plurality of values of N.

15. The method recited in claim 9, wherein K<

N, K=N, or K>

N.

16. The method recited in claim 9, wherein providing for employing the fitness function in an asymptotically optimal decoding algorithm further includes providing for updating a fitness function calculated for a previous state transition point.

17. The method recited in claim 9, wherein providing for employing the fitness function includes providing for multi-objective versions of the asymptotically optimal decoding algorithm.

18. A digital computer system configured to perform the method recited in claim 9.

19. A computer program residing on a computer-readable medium, wherein the computer program is configured to perform the method recited in claim 9.

20. The method recited in claim 9, wherein providing for employing the fitness function in an asymptotically optimal decoding algorithm comprises;

for a particular node in at least one of the plurality of state transition points, selecting a winning path terminated at a node of a previous state transition point,

producing an updated modified multiple-access code by appending one of the plurality of code-chip parameters of the particular node to a modified multiple-access code corresponding to the winning path,

calculating the fitness function for the updated modified multiple-access code to produce a fitness function parameter,

repeating the steps of selecting, producing, and calculating for each of a plurality of nodes at the previous state transition point to produce a plurality of fitness function parameters, and

selecting a winning path from one of the plurality of nodes at the previous state transition point terminating at the particular node, the winning path being selected based on one of the plurality of fitness function parameters meeting at least one predetermined criteria.

21. The method recited in claim 20, wherein the at least one predetermined criteria includes a maximum of the plurality of fitness function parameters, a minimum of the plurality of fitness function parameters, and being closest to a target fitness function parameter.

22. The method recited in claim 9, wherein a multiple-access code set is produced upon completing the asymptotically optimal decoding algorithm for the trellis, the method further comprising

providing for initializing the trellis with the multiple-access code set, and

repeating the step of providing for employing the fitness function.

23. A multiple-access coder device configured for using a Viterbi algorithm for generating at least one multiple-access code set, comprising:

a first module configured for calculating branch metrics based on at least one fitness function for possible state transitions between two successive states, and

a second module configured for calculating, as a function of said branch metrics, path metrics for possible paths constituted by successive state transitions and ending in each of said states, and for selecting, for each of said states, only a path having an optimal path-metric value.

24. A digital computer system configured to perform the method recited in claim 23.

25. A computer program residing on a computer-readable medium, wherein the computer program is configured to perform the method recited in claim 23.

26. A method for multiple-access code generation implementing an asymptotically optimal decoding algorithm type of decision algorithm, the method comprising providing for defining an initial multiple-access coding trellis, constituted by a set of nodes corresponding to possible states in a constellation of code-chip values, each node being connected to its most optimal direct antecedent node, and providing for making a trace-back of an optimum path in said trellis.

27. The method recited in claim 26, wherein providing for defining the initial multiple-access coding trellis includes providing for a code set ordered as a by-element variant topology or a by-user variant topology.

28. A digital computer system configured to perform the method recited in claim 26.

29. A computer program residing on a computer-readable medium, wherein the computer program is configured to perform the method recited in claim 26.