US 8,428,107 B1 · Code detection by using genetic algorithms

Abstract

A method for estimating an unknown spreading code in a received signal by using a set of genetic algorithms. The method comprises: selecting at least one seed of the unknown spreading code for initialization purposes, wherein the unknown spreading code comprises a plurality of chips, and performing a breeding process of the unknown spreading code by executing a breeding algorithm.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims17

Dependent claims

A method implemented in a receiver of estimating an unknown spreading code in a received signal;

said unknown spreading code comprising a plurality of chips;
said method comprising:
(A) selecting an initial code;
and
(B) performing an estimation of said unknown spreading code by performing a number of iterations, wherein for each said iteration a new generation of a seed pool is created, and wherein each said generation of said seed pool comprises a plurality of estimates of said unknown spreading code;
and wherein for each said iteration, wherein at least one said estimate of said unknown spreading code in said seed pool is tested against said target unknown spreading code and is assigned metric by:
(a) introducing a survivor threshold;
(b) performing a sorting operation to sort said plurality of said estimates of said unknown spreading code in a rank order of the assigned metrics;
(c) determining a survivor count;
and (d) keeping each said estimate of said unknown spreading code in said seed pool having a rank higher than said survivor threshold;
wherein said survivor count is a number of said estimates of said unknown spreading code each of which includes a metric that exceeds said survivor threshold;
and wherein said survivor count is said number of said estimates of said unknown spreading code that is carried forward to the next generation;
said survivor count number being an integer less than or equal to said pool size of said plurality of estimates of said unknown spreading code.

10 more elements

A method implemented in a receiver of estimating an unknown spreading code in a received signal;

said unknown spreading code comprising a plurality of chips;
said method comprising:
(A) selecting an initial code;
and
(B) performing an estimation of said unknown spreading code by executing a genetic breeding algorithm, wherein said genetic breeding algorithm is configured to use said initial code to perform said estimation of said unknown spreading code;
and wherein said genetic breeding algorithm is being built by forming a new estimate of said unknown spreading code by performing the following sub-steps:
(B1) selecting at least two progenitors;
(B2) creating random sub-groups of said progenitors;
wherein each said sub-group includes at least two said progenitors;
(B3) sub-segmenting each said progenitor belonging to said at least one randomly selected sub-group by slicing each said progenitor into a number of sub-segments;
wherein for each said progenitor from said one sub-group said firstly sliced sub-segment includes a first chip count;
wherein for each said progenitor from said one sub-group said secondly sliced sub-segment includes a second chip count;
and wherein for each said progenitor from said one sub-group said “k”-sliced sub-segment includes a “k”-th chip count;
k being an integer;
(B4) at each sequential location copying one said sub-segment from one said randomly selected progenitor into said newly created estimate of said unknown spreading code at corresponding sequential location;
and
(B6) selecting a slice as a number of non-contiguous chips of a progenitor, wherein each said non-contiguous slice of said progenitor is defined as a set of chips of one said progenitor, wherein each said chip in each said non-contiguous slice is assigned a chip sequential number;
and wherein for each said non-contiguous slice copied to an estimate of said unknown target code each said chip of one said progenitor is placed at said estimate of said unknown target code according to said chip sequential number.

15 more elements

Dependencies are inferred from the claim text.

Description4,947 words

Summary491 words

#The technology relates to the field of code detection.

#Spread spectrum techniques is a method for converting a relatively narrow band signal into a wider band signal by mixing the narrow band signal with pseudo-random noise (PRN, or spreading code). The original signal may be recovered by reversing the process. Spread spectrum techniques have several useful properties, among which is a method for sharing spectrum among multiple communications channels. Other methods of multiple access to shared spectrum include time division multiple access (TDMA) which assigns specific time periods to each transmit channel, and frequency division multiple access (FDMA) which assigns subsets of the available spectrum for each transmission channel. Spread spectrum techniques divide neither transmission time nor transmission frequency but instead allow simultaneous transmission through the selection of unique spreading code sequences for each channel—a method referred to as code division multiple access (CDMA).

#In a typical spread spectrum radio receiver, the signal received through the antenna undergoes analog processing at radio frequencies. This processing may include filtering, amplification, frequency translation and digital sampling. The signal may then require an additional frequency translation to completely remove any frequency offsets from baseband. In a mobile environment, this stage may also be responsible for eliminating the Doppler effects of moving antennas. In modern receivers, this stage is typically implemented in the digital domain, though an analog implementation is also possible.

Brief description of the drawings5 figures

#The accompanying drawings, which are incorporated in and form a part of this specification, illustrate embodiments of the technology and, together with the description, serve to explain the principles below:

#FIG. 1 is a block diagram that illustrates how a typical spread spectrum radio receiver operates.

#FIG. 2 illustrates a spread spectrum system in which the spreading code generator is implemented as a linear feedback shift register.

Detailed description4,219 words

#Reference now be made in detail to the embodiments of the technology, examples of which are illustrated in the accompanying drawings. While the present technology will be described in conjunction with the various embodiments, it will be understood that they are not intended to limit the present technology to these embodiments. On the contrary, the present technology is intended to cover alternatives, modifications and equivalents, which may be included within the spirit and scope of the various embodiments as defined by the appended claims.

#Furthermore, in the following detailed description, numerous specific-details are set forth in order to provide a thorough understanding of the presented embodiments. However, it will be obvious to one of ordinary skill in the art that the presented embodiments may be practiced without these specific details. In other instances, well known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the presented embodiments.

#FIG. 1 is a block diagram 10 that illustrates how a typical spread spectrum radio receiver operates. The signal is received through the antenna 12 and may undergo analog processing 14 at radio frequencies. This processing may include filtering, amplification, frequency translation and digital sampling. The signal may then require an additional frequency translation at block 16 to completely remove any frequency offsets from baseband. In a mobile environment, this stage may also be responsible for eliminating the Doppler effects of moving antennas. In modern receivers, this stage is typically implemented in the digital domain, though an analog implementation is also feasible.

Facts

Application

12/218,897Filed 17 Jul 2008 · us provisional application

Priority

11 May 2008

Granted

23 Apr 2013

Term ends

31 Dec 2030

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 897 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification2 codes

G06N 3/126
Using genetic models: evolutionary algorithms, e.g. genetic algorithms or genetic programming
G06N
AI and machine learning

Timeline

11 May 2008Priority claimedParent application 61/127,351
17 Jul 2008Application filedUS 12/218,897
14 Nov 2008Assigned to Trimble Navigation, Ltd.assignment of assignor's interest
23 Apr 2013GrantedUS 8,428,107 B1
12 Oct 2026TodayWithin its term
31 Dec 2030Term endsEstimated, includes 897 days of adjustment

Code detection by using genetic algorithms

Life of this patent

Code detection by using genetic algorithms

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims17

Description4,947 words

Drawings

Classification2 codes

Life of this patent

Description4,947 words