Title of Invention	A METHOD FOR DEVELOPING AN ORTHOGONAL SEQUENCE FOR TRAINING A RECEIVER
Abstract	Use of a training sequence having terms that are orthogonal to each other are employed to considerably speed up execution of the LMS algorithm. Such orthogonal sequences are developed for a channel that is described as a finite impulse response (FIR) filter having a length Mnew-fiom the already existing orthogonal training sequences for at least two channels that have respective lengths Moldl and Mold2 each that is less than M^ such that the product of Moldl and Mold2 is equal to Mnew when Mold2 and Mold2 have no common prime number factor. More specifically, a set of initial existing orthogonal training sequences is found, e.g., using those that were known in the prior art or by performing a computer search over known symbol constellations given a channel of length M. Thereafter, an orthogonal training sequence of length Mnew is developed, where the product of MoMI and Mold2 is equal to Mnew by repeating the training sequence oldl Mold2 number of times to form a first concatenated sequence and repeating the training sequence old2 MoWl number of times to form a second concatenated sequence, so that both the first concatenated sequence and the second concatenated sequence have the same length. Each term of the first concatenated sequence is multiplied by the correspondingly located term in the second concatenated sequence which is placed in the same location in a new sequence made up of the resulting Mnew products. This new sequence is an orthogonal sequence of length Mnew. Fig 1

Title of Invention

A METHOD FOR DEVELOPING AN ORTHOGONAL SEQUENCE FOR TRAINING A RECEIVER

Abstract

Use of a training sequence having terms that are orthogonal to each other are employed to considerably speed up execution of the LMS algorithm. Such orthogonal sequences are developed for a channel that is described as a finite impulse response (FIR) filter having a length Mnew-fiom the already existing orthogonal training sequences for at least two channels that have respective lengths Moldl and Mold2 each that is less than M^ such that the product of Moldl and Mold2 is equal to Mnew when Mold2 and Mold2 have no common prime number factor. More specifically, a set of initial existing orthogonal training sequences is found, e.g., using those that were known in the prior art or by performing a computer search over known symbol constellations given a channel of length M. Thereafter, an orthogonal training sequence of length Mnew is developed, where the product of MoMI and Mold2 is equal to Mnew by repeating the training sequence oldl Mold2 number of times to form a first concatenated sequence and repeating the training sequence old2 MoWl number of times to form a second concatenated sequence, so that both the first concatenated sequence and the second concatenated sequence have the same length. Each term of the first concatenated sequence is multiplied by the correspondingly located term in the second concatenated sequence which is placed in the same location in a new sequence made up of the resulting Mnew products. This new sequence is an orthogonal sequence of length Mnew. Fig 1

Full Text	This invention relates-to the art of training a receiver that receives signals from a channel that introduces noise and intersymbol interference, and in particular, to a system of generating the training sequence so that training may be performed using the least mean squares (LMS) algorithm with low latency. Background of the Invention A problem in the art of training a receiver that a) receives signals from a channel that introduces noise and intersymbol interference and b) which uses the least mean squares (LMS) algorithm, is that the high speed of computation required to perform the LMS algorithm Limits the transmission rate for data. Therefore, the prior art uses a small step size so that the computation is approximately the same as if the elements of the training sequence were orthogonal. However, this approach leads to a coarser channel estimate, and the training takes longer than is desirable due to the small step size. Summary of the Invention I have recognized that if the terms of the training sequence could actually be orthogonal to each other then the LMS algorithm can be speeded up considerably. Some orthogonal sequences have been found, but these are limited to particular conditions, e.g., certain lengths or the modulation scheme for which they could be used do not correspond to conventionally used modulation arrangements. However, there has been no method to develop training sequences that indeed have orthogonal terms given the number of weights needed to properly describe the channel as a finite impulse response (FIR) filter. Therefore, in accordance with the principles of the invention, I have devised a process by which an orthogonal training sequence can be developed for a channel that is described as a finite impulse response (FIR) filter having a length Mnew from the already existing orthogonal training sequences for at least two channels that have respective lengths M0[dl and MoId2 each that is less than Mncw such that the product of Mold1 and Mold2 is equal to Mnew when Moldl and M0ld2 have no common prime number factor More specifically, a set of initial existing orthogonal training sequences is found, e.g., using those that were known in the prior art or by performing a computer search over known symbol constellations given a channel of length M. Thereafter, an orthogonal training sequence of length Mnew is developed, where the product of Moldl and M,^ is equal to Mnew by repeating the training sequence old 1 Mold2 number of times to form a first concatenated sequence and repeating the training sequence old2 Moldl number of times to form a second concatenated sequence, so that both the first concatenated sequence and the second concatenated sequence have the same length. Each term of the first concatenated sequence is multiplied by the correspondingly located term in the second concatenated sequence which is placed in the same location in a new sequence made up of the resulting Mnew products. This new sequence is an orthogonal sequence of length Mnew. If there is more than one existing orthogonal sequence for a particular length channel, e.g., there may be different orthogonal sequences for different modulation schemes for the same length channel, the implementer may choose which ever orthogonal sequence gives the results desired. Often, for practical applications, the result that yields the modulation scheme that is most suitable for use with the actual channel, which may yield the highest speeds, or the result that yields the smallest alphabet, which would reduce the hardware required for implementation, is desirable. Advantageously, a receiver using such an orthogonal training sequence may employ the optimum step size, resulting in the fastest training. Brief Description of the Drawing In the drawing: FIG. 1 shows, in flowchart form, an exemplary process for developing an orthogonal training sequence in accordance with the principles of the invention; and FIG. 2 shows an exemplary receiver arranged in accordance with the principles of the invention. Detailed Description The following merely illustrates the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements which, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope. Furthermore, all examples and conditional language recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure. Thus, for example, it will be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudocode, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown. The functions of the various elements shown in the FIGs., including functional blocks labeled as "processors", may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term "processor" or "controller" should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional and/or custom, may also be included. Similarly, any switches shown in the FIG£ ar6 conceptual only. Their function may be carried out through the operation of program logic> through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementer as more specifically understood from the context. In the claims hereof any element expressed as a means for performing a specified function is intended to encompass any way of performing that function including, for example, a) a combination of circuit elements which performs that function or b) software in any form, including, therefore, firmware, microcode or the like, combined with appropriate circuitry for executing that software to perform the function. The invention as defined by such claims resides in the fact that the functionalities provided by the various recited means are combined and brought together in the manner which the claims call for. Applicant thus regards any means which can provide those functionalities as equivalent as those shown herein. Unless otherwise explicitly specified herein, the drawings are not drawn to scale, FIG. 1 shows, in flowchart form, an exemplary process for developing an orthogonal training sequence can be developed for a channel that is described as a finite impulse response (FIR) filter having a length Mnew from already existing orthogonal training sequences for at least two channels that have respective lengths MoJd, and M0[d2 each that is less than Mnew such that the product of M0ld1 and Mold2 is equal to M^ when Mo!d1 & M0ld2 have no common prime number factor. The process is entered in step 101 when a new training sequence is required, e.g., when developing a new wireless communication system. Next, in step 103, two already existing orthogonal training sequences oldl and o!d2 for at least two channels that have respective lengths Mo!di and Mold2 each that is less than Mncw such that the product of Mold1 and Mold2 is equal to Mncw when Mold1 and Mold2 have no common prime number factor is selected. If it is not possible to find values such that the product of Mo!dl and Mo!d2 is equal to Mnew, e.g., M„ew is a prime number, then the process must terminate in an error condition. However, from a practical point of view, typically using a larger value of Mnew rather than the exact value of Mnew being sought will yield adequate results. The initial orthogonal sequences may be obtained by performing an exhaustive search over each possible combination for a particular modulation scheme's alphabet and a given channel length to determine the existence of an orthogonal training sequence. Not all such searches will yield an orthogonal sequence, e.g., no such sequence has yet been found for a channel length of 13. Also, the time required to conduct each such searches may be quite long. Those orthogonal sequences that have been found to date are shown in Table 1. In particular, Table 1 shows exemplary orthogonal sequences and the corresponding lengths and modulation schemes for which they were found. Note that Table 1 also includes the length 4 and length 16 orthogonal sequences that were known in the prior art Adder 203 sums the outputs of each of parallel weight computers 201, i.e., each corresponding position of the vectors that are output by parallel weight computers 201 are summed. The summation vector produced as an output by adder 203 is supplied to multiplier 205 which multiplies each element of the summation vector by the step size ji, thus scaling the summation vector by p.. The scaled summation vector is then supplied to new weight vector producer 207, which adds the scaled summation vector to the previously produced weight vector, which was stored in new weight vector producer 207, and supplies the resulting value as the new weight, as well as storing it. Note that the orthogonal sequences referred to herein as orthogonal training sequences need not actually ever have been used for training, although typically they are suitable for use as training sequences. Furthermore, the orthogonal sequences may be used for synchronization purposes. WE CLAIM : 1. A method for developing a new orthogonal sequence for training a receiver that receives signal from channel, said channel being described as a finite impulse response (FIR) filter having a length Mnew, said channel introducing noise and inter symbol interference in said signals, the sequence developed according to the method comprising the steps of: selecting first and second existing orthogonal sequences old\| and old2 for at least two channels that have respective lengths Mold1 and Mold2, the product of M0idl and M0id2 being equal to Mnew and Mold1 and Mold2 having no common prime number factor; repeating the sequence old1 Mold2 number of times to form a first concatenated sequence; repeating the sequence 01d2 Mold1 number of times to form a second concatenated sequence; multiplying each term in said first concatenated sequence by a correspondingly located term in said second concatenated sequence; and forming said new sequence by placing each product produced in said multiplying step into a corresponding location therein. 2. The method as claimed in claim 1 comprising the step of performing a search over each possible combination for a particular modulation scheme's alphabet and a given channel length to determine the existence of an orthogonal sequence for use in said selecting step. 3. The method as claimed in claim 1 wherein at least one of said first existing orthogonal sequence, said second existing orthogonal sequence, and said new orthogonal sequence is employed as a training sequence. 4. The method as claimed in claim 1 wherein at least one of said first existing orthogonal sequence, said second existing orthogonal sequence, and said new orthogonal sequence is employed as a synchronization sequence. 5. The method as claimed in claim 1 wherein first and second existing orthogonal sequences each have a length that has no common prime number factor with the other. 6. A receiver comprising a plurality of parallel weight computers (201) an adder (203) coupled to receive and add the outputs of said parallel weight computers; a multiplier (205) for scaling by a step size a vector produced as an output by said adder; and a new weight vector producer (207) for supplying as an output a new weight vector as a function of a previously weight vector and a scaled vector supplied by said multiplier. 7. The receiver as claimed in claim 6 wherein the said receiver is adapted to receive the orthogonal sequence developed by the method as claimed in Claim 1 and to employ said new orthogonal sequence as a training sequence. 8. The receiver as claimed in claim 6 wherein the said receiver is adapted to receive the orthogonal sequence developed by the method as claimed in Claim 1 and to employ said new orthogonal sequence as a synchronization sequence.

Full Text

This invention relates-to the art of training a receiver that receives signals from a channel that introduces noise and intersymbol interference, and in particular, to a system of generating the training sequence so that training may be performed using the least mean squares (LMS) algorithm with low latency.
Background of the Invention
A problem in the art of training a receiver that a) receives signals from a channel that introduces noise and intersymbol interference and b) which uses the least mean squares (LMS) algorithm, is that the high speed of computation required to perform the LMS algorithm Limits the transmission rate for data. Therefore, the prior art uses a small step size so that the computation is approximately the same as if the elements of the training sequence were orthogonal. However, this approach leads to a coarser channel estimate, and the training takes longer than is desirable due to the small step size.
Summary of the Invention
I have recognized that if the terms of the training sequence could actually be orthogonal to each other then the LMS algorithm can be speeded up considerably. Some orthogonal sequences have been found, but these are limited to particular conditions, e.g., certain lengths or the modulation scheme for which they could be used do not correspond to conventionally used modulation arrangements. However, there has been no method to develop training sequences that indeed have orthogonal terms given the number of weights needed to properly describe the channel as a finite impulse response (FIR) filter.
Therefore, in accordance with the principles of the invention, I have devised a process by which an orthogonal training sequence can be developed for a channel that is described as a finite impulse response (FIR) filter having a length Mnew from the already existing orthogonal training sequences for at least two channels that have respective lengths M0[dl and MoId2 each that is less than Mncw such that the product of Mold1 and Mold2

is equal to Mnew when Moldl and M0ld2 have no common prime number factor More specifically, a set of initial existing orthogonal training sequences is found, e.g., using those that were known in the prior art or by performing a computer search over known symbol constellations given a channel of length M. Thereafter, an orthogonal training sequence of length Mnew is developed, where the product of Moldl and M,^ is equal to Mnew by repeating the training sequence old 1 Mold2 number of times to form a first concatenated sequence and repeating the training sequence old2 Moldl number of times to form a second concatenated sequence, so that both the first concatenated sequence and the second concatenated sequence have the same length. Each term of the first concatenated sequence is multiplied by the correspondingly located term in the second concatenated sequence which is placed in the same location in a new sequence made up of the resulting Mnew products. This new sequence is an orthogonal sequence of length Mnew. If there is more than one existing orthogonal sequence for a particular length channel, e.g., there may be different orthogonal sequences for different modulation schemes for the same length channel, the implementer may choose which ever orthogonal sequence gives the results desired. Often, for practical applications, the result that yields the modulation scheme that is most suitable for use with the actual channel, which may yield the highest speeds, or the result that yields the smallest alphabet, which would reduce the hardware required for implementation, is desirable.
Advantageously, a receiver using such an orthogonal training sequence may employ the optimum step size, resulting in the fastest training.
Brief Description of the Drawing
In the drawing:
FIG. 1 shows, in flowchart form, an exemplary process for developing an orthogonal training sequence in accordance with the principles of the invention; and
FIG. 2 shows an exemplary receiver arranged in accordance with the principles of the invention.

Detailed Description
The following merely illustrates the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements which, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope. Furthermore, all examples and conditional language recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure.
Thus, for example, it will be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudocode, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.
The functions of the various elements shown in the FIGs., including functional blocks labeled as "processors", may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term "processor" or "controller" should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional and/or custom, may also be included.

Similarly, any switches shown in the FIG£ ar6 conceptual only. Their function may be carried out through the operation of program logic> through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementer as more specifically understood from the context.
In the claims hereof any element expressed as a means for performing a specified function is intended to encompass any way of performing that function including, for example, a) a combination of circuit elements which performs that function or b) software in any form, including, therefore, firmware, microcode or the like, combined with appropriate circuitry for executing that software to perform the function. The invention as defined by such claims resides in the fact that the functionalities provided by the various recited means are combined and brought together in the manner which the claims call for. Applicant thus regards any means which can provide those functionalities as equivalent as those shown herein.
Unless otherwise explicitly specified herein, the drawings are not drawn to scale, FIG. 1 shows, in flowchart form, an exemplary process for developing an orthogonal training sequence can be developed for a channel that is described as a finite impulse response (FIR) filter having a length Mnew from already existing orthogonal training sequences for at least two channels that have respective lengths MoJd, and M0[d2 each that is less than Mnew such that the product of M0ld1 and Mold2 is equal to M^ when Mo!d1 & M0ld2 have no common prime number factor. The process is entered in step 101 when a new training sequence is required, e.g., when developing a new wireless communication system. Next, in step 103, two already existing orthogonal training sequences oldl and o!d2 for at least two channels that have respective lengths Mo!di and Mold2 each that is less than Mncw such that the product of Mold1 and Mold2 is equal to Mncw when Mold1 and Mold2 have no common prime number factor is selected. If it is not possible to find values such that the product of Mo!dl and Mo!d2 is equal to Mnew, e.g., M„ew is a prime number, then the process must terminate in an error condition. However, from a practical point of view, typically using a larger value of Mnew rather than the exact value of Mnew being sought will yield adequate results.

The initial orthogonal sequences may be obtained by performing an exhaustive search over each possible combination for a particular modulation scheme's alphabet and a given channel length to determine the existence of an orthogonal training sequence. Not all such searches will yield an orthogonal sequence, e.g., no such sequence has yet been found for a channel length of 13. Also, the time required to conduct each such searches may be quite long. Those orthogonal sequences that have been found to date are shown in Table 1. In particular, Table 1 shows exemplary orthogonal sequences and the corresponding lengths and modulation schemes for which they were found. Note that Table 1 also includes the length 4 and length 16 orthogonal sequences that were known in the prior art

Adder 203 sums the outputs of each of parallel weight computers 201, i.e., each corresponding position of the vectors that are output by parallel weight computers 201 are summed. The summation vector produced as an output by adder 203 is supplied to multiplier 205 which multiplies each element of the summation vector by the step size ji, thus scaling the summation vector by p.. The scaled summation vector is then supplied to new weight vector producer 207, which adds the scaled summation vector to the previously produced weight vector, which was stored in new weight vector producer 207, and supplies the resulting value as the new weight, as well as storing it.
Note that the orthogonal sequences referred to herein as orthogonal training sequences need not actually ever have been used for training, although typically they are suitable for use as training sequences. Furthermore, the orthogonal sequences may be used for synchronization purposes.

WE CLAIM :
1. A method for developing a new orthogonal sequence for training a receiver that
receives signal from channel, said channel being described as a finite impulse
response (FIR) filter having a length Mnew, said channel introducing noise and inter
symbol interference in said signals, the sequence developed according to the method
comprising the steps of:
selecting first and second existing orthogonal sequences old| and old2 for at least two channels that have respective lengths Mold1 and Mold2, the product of M0idl and M0id2 being equal to Mnew and Mold1 and Mold2 having no common prime number factor;
repeating the sequence old1 Mold2 number of times to form a first concatenated sequence;
repeating the sequence 01d2 Mold1 number of times to form a second concatenated sequence;
multiplying each term in said first concatenated sequence by a correspondingly located term in said second concatenated sequence; and
forming said new sequence by placing each product produced in said multiplying step into a corresponding location therein.
2. The method as claimed in claim 1 comprising the step of performing a search over each possible combination for a particular modulation scheme's alphabet and a given channel length to determine the existence of an orthogonal sequence for use in said selecting step.
3. The method as claimed in claim 1 wherein at least one of said first existing orthogonal sequence, said second existing orthogonal sequence, and said new orthogonal sequence is employed as a training sequence.

4. The method as claimed in claim 1 wherein at least one of said first existing
orthogonal sequence, said second existing orthogonal sequence, and said new
orthogonal sequence is employed as a synchronization sequence.
5. The method as claimed in claim 1 wherein first and second existing orthogonal
sequences each have a length that has no common prime number factor with the other.
6. A receiver comprising
a plurality of parallel weight computers (201)
an adder (203) coupled to receive and add the outputs of said parallel weight computers;
a multiplier (205) for scaling by a step size a vector produced as an output by said adder; and
a new weight vector producer (207) for supplying as an output a new weight vector as a function of a previously weight vector and a scaled vector supplied by said multiplier.
7. The receiver as claimed in claim 6 wherein the said receiver is adapted to
receive the orthogonal sequence developed by the method as claimed in Claim 1 and
to employ said new orthogonal sequence as a training sequence.
8. The receiver as claimed in claim 6 wherein the said receiver is adapted to
receive the orthogonal sequence developed by the method as claimed in Claim 1 and
to employ said new orthogonal sequence as a synchronization sequence.

Documents:

696-mas-2001 abstract-duplicate.pdf

696-mas-2001 claims-duplicate.pdf

696-mas-2001 description (complete)-duplicate.pdf

696-mas-2001 drawings-duplicate.pdf

696-mas-2001-abstract.pdf

696-mas-2001-claims.pdf

696-mas-2001-correspondence others.pdf

696-mas-2001-correspondence po.pdf

696-mas-2001-description comeplete.pdf

696-mas-2001-drawings.pdf

696-mas-2001-form 1.pdf

696-mas-2001-form 18.pdf

696-mas-2001-form 26.pdf

696-mas-2001-form 3.pdf

696-mas-2001-form 5.pdf

abs-696-mas-2001.jpg

« Previous Patent

Next Patent »

Patent Number

222515

Indian Patent Application Number

696/MAS/2001

PG Journal Number

47/2008

Publication Date

21-Nov-2008

Grant Date

14-Aug-2008

Date of Filing

24-Aug-2001

Name of Patentee

LUCENT TECHNOLOGIES INC.

Applicant Address

600 MOUNTAIN AVENUE, MURRAY HILL, NEW JERSEY 07974-0636,

Inventors:

#	Inventor's Name	Inventor's Address
1	MARKUS RUPP	ZADELSTEDE 1-10, NIEUWEGEIN, 3431 JZ,

PCT International Classification Number

H04B3/23

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	09/648983	2000-08-28	U.S.A.