US20080109696A1

Movatterモバイル変換

Info

Publication number: US20080109696A1
Application number: US11/981,305
Authority: US
Inventors: Ismail Lakkis
Original assignee: Pulse Link Inc
Current assignee: Intellectual Ventures Holding 81 LLC
Priority date: 2001-12-06
Filing date: 2007-10-31
Publication date: 2008-05-08
Also published as: US20050201315A1; WO2006036332A1; US7406647B2

Abstract

A forward error correction encoder encodes input data words into code words that comprise a parity matrix. In one aspect, the encoder is optimized based on the properties of the parity matrix in order to reduce routing overhead and size.

Description

RELATED APPLICATIONS INFORMATION

This application claims priority under 35 U.S.C. §120 as a continuation of U.S. patent application Ser. No. 10/952,485, entitled, “Systems and Methods for Forward Error Correction in a Wireless Communication Network,” filed Sep. 27, 2004, which is a continuation-in-part of U.S. patent application Ser. No. 10/120,456, entitled, “Systems and Methods for Recovering Bandwidth in a Wireless Communication Network,” filed Apr. 9, 2002, which is in turn a continuation-in-part of U.S. patent application Ser. No. 10/010,601, entitled, “Systems and Methods for Wireless Communication Over A Wide Bandwidth Channel Using A Plurality of Sub-channels filed on Dec. 6, 2001, now U.S. Pat. No. 7,289,494, both of which are incorporated herein by reference in the entirety as if set forth in full.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates generally to wireless communication and more particularly to systems and methods for wireless communication over a wide bandwidth channel using a plurality of sub-channels.

2. Background

Wireless communication systems are proliferating at the Wide Area Network (WAN), Local Area Network (LAN), and Personal Area Network (PAN) levels. These wireless communication systems use a variety of techniques to allow simultaneous access to multiple users. The most common of these techniques are Frequency Division Multiple Access (FDMA), which assigns specific frequencies to each user, Time Division Multiple Access (TDMA), which assigns particular time slots to each user, and Code Division Multiple Access (CDMA), which assigns specific codes to each user. But these wireless communication systems and various modulation techniques are afflicted by a host of problems that limit the capacity and the quality of service provided to the users. The following paragraphs briefly describe a few of these problems for the purpose of illustration.

One problem that can exist in a wireless communication system is multipath interference. Multipath interference, or multipath, occurs because some of the energy in a transmitted wireless signal bounces off of obstacles, such as buildings or mountains, as it travels from source to destination. The obstacles in effect create reflections of the transmitted signal and the more obstacles there are, the more reflections they generate. The reflections then travel along their own transmission paths to the destination (or receiver). The reflections will contain the same information as the original signal; however, because of the differing transmission path lengths, the reflected signals will be out of phase with the original signal. As a result, they will often combine destructively with the original signal in the receiver. This is referred to as fading. To combat fading, current systems typically try to estimate the multipath effects and then compensate for them in the receiver using an equalizer. In practice, however, it is very difficult to achieve effective multipath compensation.

A second problem that can affect the operation of wireless communication systems is interference from adjacent communication cells within the system. In FDMA/TDMA systems, this type of interference is prevented through a frequency reuse plan. Under a frequency reuse plan, available communication frequencies are allocated to communication cells within the communication system such that the same frequency will not be used in adjacent cells. Essentially, the available frequencies are split into groups. The number of groups is termed the reuse factor. Then the communication cells are grouped into clusters, each cluster containing the same number of cells as there are frequency groups. Each frequency group is then assigned to a cell in each cluster. Thus, if a frequency reuse factor of 7 is used, for example, then a particular communication frequency will be used only once in every seven communication cells. As a result, in any group of seven communication cells, each cell can only use 1/7^thof the available frequencies, i.e., each cell is only able to use 1/7^thof the available bandwidth.

In a CDMA communication system, each cell uses the same wideband communication channel. In order to avoid interference with adjacent cells, each communication cell uses a particular set of spread spectrum codes to differentiate communications within the cell from those originating outside of the cell. Thus, CDMA systems preserve the bandwidth in the sense that they avoid limitations inherent to conventional reuse planning. But as will be discussed, there are other issues that limit the bandwidth in CDMA systems as well

Thus, in overcoming interference, system bandwidth is often sacrificed. Bandwidth is becoming a very valuable commodity as wireless communication systems continue to expand by adding more and more users. Therefore, trading off bandwidth for system performance is a costly, albeit necessary, proposition that is inherent in all wireless communication systems.

The foregoing are just two examples of the types of problems that can affect conventional wireless communication systems. The examples also illustrate that there are many aspects of wireless communication system performance that can be improved through systems and methods that, for example, reduce interference, increase bandwidth, or both.

Not only are conventional wireless communication systems effected by problems, such as those described in the preceding paragraphs, but also different types of systems are effected in different ways and to different degrees. Wireless communication systems can be split into three types: 1) line-of-sight systems, which can include point-to-point or point-to-multipoint systems; 2) indoor non-line of sight systems; and 3) outdoor systems such as wireless WANs. Line-of-sight systems are least affected by the problems described above, while indoor systems are more affected, due for example to signals bouncing off of building walls. Outdoor systems are by far the most affected of the three systems. Because these types of problems are limiting factors in the design of wireless transmitters and receivers, such designs must be tailored to the specific types of system in which it will operate. In practice, each type of system implements unique communication standards that address the issues unique to the particular type of system. Even if an indoor system used the same communication protocols and modulation techniques as an outdoor system, for example, the receiver designs would still be different because multipath and other problems are unique to a given type of system and must be addressed with unique solutions. This would not necessarily be the case if cost efficient and effective methodologies can be developed to combat such problems as described above that build in programmability so that a device can be reconfigured for different types of systems and still maintain superior performance.

SUMMARY OF THE INVENTION

In another aspect, decoder is optimized to receive and decode the code word in the face of noise introduced when the code word is transmitted over the physical channel

Other aspects, advantages, and novel features of the invention will become apparent from the following Detailed Description of Preferred Embodiments, when considered in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

Preferred embodiments of the present inventions taught herein are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings, in which:

FIG. 1 is a diagram illustrating an example embodiment of a wideband channel divided into a plurality of sub-channels in accordance with the invention;

FIG. 2 is a diagram illustrating the effects of multipath in a wireless communication system;

FIG. 3 is a diagram illustrating another example embodiment of a wideband communication channel divided into a plurality of sub-channels in accordance with the invention;

FIG. 4 is a diagram illustrating the application of a roll-off factor to the sub-channels ofFIGS. 1, 2 and3;

FIG. 5A is a diagram illustrating the assignment of sub-channels for a wideband communication channel in accordance with the invention;

FIG. 5B is a diagram illustrating the assignment of time slots for a wideband communication channel in accordance with the invention;

FIG. 6 is a diagram illustrating an example embodiment of a wireless communication in accordance with the invention;

FIG. 7 is a diagram illustrating the use of synchronization codes in the wireless communication system ofFIG. 6 in accordance with the invention;

FIG. 8 is a diagram illustrating a correlator that can be used to correlate synchronization codes in the wireless communication system ofFIG. 6;

FIG. 9 is a diagram illustrating synchronization code correlation in accordance with the invention;

FIG. 10 is a diagram illustrating the cross-correlation properties of synchronization codes configured in accordance with the invention;

FIG. 11 is a diagram illustrating another example embodiment of a wireless communication system in accordance with the invention;

FIG. 12A is a diagram illustrating how sub-channels of a wideband communication channel according to the present invention can be grouped in accordance with the present invention;

FIG. 12B is a diagram illustrating the assignment of the groups of sub-channels ofFIG. 12A in accordance with the invention;

FIG. 13 is a diagram illustrating the group assignments ofFIG. 12B in the time domain;

FIG. 14 is a flow chart illustrating the assignment of sub-channels based on SIR measurements in the wireless communication system ofFIG. 11 in accordance with the invention;

FIG. 15 is a logical block diagram of an example embodiment of transmitter configured in accordance with the invention;

FIG. 16 is a logical block diagram of an example embodiment of a modulator configured in accordance with the present invention for use in the transmitter ofFIG. 15;

FIG. 17 is a diagram illustrating an example embodiment of a rate controller configured in accordance with the invention for use in the modulator ofFIG. 16;

FIG. 18 is a diagram illustrating another example embodiment of a rate controller configured in accordance with the invention for use in the modulator ofFIG. 16;

FIG. 19 is a diagram illustrating an example embodiment of a frequency encoder configured in accordance with the invention for use in the modulator ofFIG. 16;

FIG. 20 is a logical block diagram of an example embodiment of a TDM/FDM block configured in accordance with the invention for use in the modulator ofFIG. 16;

FIG. 21 is a logical block diagram of another example embodiment of a TDM/FDM block configured in accordance with the invention for use in the modulator ofFIG. 16;

FIG. 22 is a logical block diagram of an example embodiment of a frequency shifter configured in accordance with the invention for use in the modulator ofFIG. 16;

FIG. 23 is a logical block diagram of a receiver configured in accordance with the invention;

FIG. 24 is a logical block diagram of an example embodiment of a demodulator;

FIG. 25 is a logical block diagram of an example embodiment of an equalizer configured in accordance with the present invention for use in the demodulator ofFIG. 24;

FIG. 26 is a logical block diagram of an example embodiment of a wireless communication device configured in accordance with the invention;

FIG. 27 is a flow chart illustrating an exemplary method for recovering bandwidth in a wireless communication network in accordance with the invention;

FIG. 28 is a diagram illustrating an exemplary wireless communication network in which the method ofFIG. 27 can be implemented;

FIG. 29 is a logical block diagram illustrating an exemplary transmitter that can be used in the network ofFIG. 28 to implement the method ofFIG. 27;

FIG. 30 is a logical block diagram illustrating another exemplary transmitter that can be used in the network ofFIG. 28 to implement the method ofFIG. 27;

FIG. 31 is a diagram illustrating another exemplary wireless communication network in which the method ofFIG. 27 can be implemented;

FIG. 32 is a diagram illustrating an exemplary FEC encoder and exemplary FEC decoder;

FIG. 33 is a diagram illustrating an example FEC encoder configured in accordance with one embodiment;

FIG. 34 is a diagram illustrating a FEC encoder configured to generated a code word from input data in accordance with one embodiment;

FIG. 35 is a diagram illustrating the encoder ofFIG. 34 in more detail;

FIG. 36 is a diagram illustrating further detail for the encoder ofFIG. 34;

FIG. 37 is a diagram illustrating an example parity node processor that can be included in a decoder in accordance with one embodiment;

FIG. 38 is a diagram illustrating one node of the parity node processor ofFIG. 37;

FIG. 39 is a diagram illustrating the parity node processor ofFIG. 37 in more detail; and

FIG. 40 is a diagram illustrating a parity node processor configured in accordance with one embodiment.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

I. Introduction

In order to improve wireless communication system performance and allow a single device to move from one type of system to another, while still maintaining superior performance, the systems and methods described herein provide various communication methodologies that enhance performance of transmitters and receivers with regard to various common problems that afflict such systems and that allow the transmitters and/or receivers to be reconfigured for optimal performance in a variety of systems. Accordingly, the systems and methods described herein define a channel access protocol that uses a common wideband communication channel for all communication cells. The wideband channel, however, is then divided into a plurality of sub-channels. Different sub-channels are then assigned to one or more users within each cell. But the base station, or service access point, within each cell transmits one message that occupies the entire bandwidth of the wideband channel. Each user's communication device receives the entire message, but only decodes those portions of the message that reside in sub-channels assigned to the user. For a point-to-point system, for example, a single user may be assigned all sub-channels and, therefore, has the full wide band channel available to them. In a wireless WAN, on the other hand, the sub-channels may be divided among a plurality of users,

In the descriptions of example embodiments that follow, implementation differences, or unique concerns, relating to different types of systems will be pointed out to the extent possible. But it should be understood that the systems and methods described herein are applicable to any type of communication systems. In addition, terms such as communication cell, base station, service access point, etc. are used interchangeably to refer to the common aspects of networks at these different levels.

To begin illustrating the advantages of the systems and methods described herein, one can start by looking at the multipath effects for a singlewideband communication channel100 of bandwidth B as shown inFIG. 1. Communications sent overchannel100 in a traditional wireless communication system will comprise digital data symbols, or symbols, that are encoded and modulated onto a RF carrier that is centered at frequency f_cand occupies bandwidth B. Generally, the width of the symbols (or the symbol duration) T is defined as 1/B. Thus, if the bandwidth B is equal to 100 MHz, then the symbol duration T is defined by the following equation:
T=1/B= 1/200 MHZ=10 ns. (1)

When a receiver receives the communication, demodulates it, and then decodes it, it will recreate astream104 ofdata symbols106 as illustrated inFIG. 2. But the receiver will also receivemultipath versions108 of the same data stream. Because multipath data streams108 are delayed in time relative todata stream104 by delays d1, d2, d3, and d4, for example, they may combine destructively withdata stream104.

A delay spread d_sis defined as the delay from reception ofdata stream104 to the reception of the lastmultipath data stream108 that interferes with the reception ofdata stream104, Thus, in the example illustrated inFIG. 2, the delay spread d_sis equal to delay d4. The delay spread d_swill vary for, different environments. An environment with a lot of obstacles will create a lot of multipath reflections. Thus, the delay spread d_swill be longer. Experiments have shown that for outdoor WAN type environments, the delay spread d_scan be as long as 20 μs. Using the 10 ns symbol duration of equation (1), this translates to 2000 symbols. Thus, with a very large bandwidth, such as 100 MHz, multipath interference can cause a significant amount of interference at the symbol level for which adequate compensation is difficult to achieve. This is true even for indoor environments. For indoor LAN type systems, the delay spread d_sis significantly shorter, typically about 1 μs. For a 10 nm symbol duration, this is equivalent to 100 symbols, which is more manageable but still significant.

By segmenting the bandwidth B into a plurality of sub-channels200, as illustrated inFIG. 3, and generating a distinct data stream for each sub-channel, the multipath effect can be reduced to a much more manageable level. For example, if the bandwidth B of each sub-channel200 is 500 KHz, then the symbol duration is 2 μs. Thus, the delay spread d_sfor each sub-channel is equivalent to only 10 symbols (outdoor) or half a symbol (indoor). Thus, by breaking up a message that occupies the entire bandwidth B into discrete messages, each occupying the bandwidth B of sub-channels200, a very wideband signal that suffers from relatively minor multipath effects is created.

Before discussing further features, and advantages of using a wideband communication channel segmented into a plurality of sub-channels as described, certain aspects of the sub-channels will be explained in more detail. Referring back toFIG. 3, the overall bandwidth B is segmented into N sub-channels center at frequencies f₀to f_N-1. Thus, the sub-channel200 that is immediately to the right of fc is offset from fc by b/2, where b is the bandwidth of each sub-channel200. The next sub-channel200 is offset by 3b/2, the next by 5b/2, and so on. To the left of fc, each sub-channel200 is offset by −b/s, −3b/s, −5b/2, etc

Preferably, sub-channels200 are non-overlapping as this allows each sub-channel to be processed independently in the receiver. To accomplish this, a roll-off factor is preferably applied to the signals in each sub-channel in a pulse-shaping step. The effect of such a pulse-shaping step is illustrated inFIG. 3 by the non-rectangular shape of the pulses in each sub-channel200. Thus, the bandwidth B of each sub-channel can be represented by an equation such as the following:
b=(1+r)/T, (2)

- Where r=the roll-off factor; and

T=the symbol duration.

Without the roll-off factor, i.e., b=1/T, the pulse shape would be rectangular in the frequency domain, which corresponds to a ((sin x)/x)ˆ2 function in the time domain. The time domain signal for a ((sin x)/x)ˆ2signal400 is shown inFIG. 4 in order to illustrate the problems associated with a rectangular pulse shape and the need to use a roll-off factor.

As can be seen,main lobe402 comprises almost all ofsignal400. But some of the signal also resides inside lobes404, which stretch out indefinitely in both directions frommain lobe402.Side lobes404 make processing signal400 much more difficult, which increases the complexity of the receiver. Applying a roll-off factor r, as in equation (2), causes signal400 to decay faster, reducing the number ofside lobes404. Thus, increasing the roll-off factor decreases the length ofsignal400, i.e., signal400 becomes shorter in time. But including the roll-off factor also decreases the available bandwidth in each sub-channel200. Therefore, r must be selected so as to reduce the number ofside lobes404 to a sufficient number, e.g., 15, while still maximizing the available bandwidth in each sub-channel200.

Thus, the overall bandwidth B for communication channel200 is given by the following equation:
B=N(1+r)/T; (3)
or
B=M/T, (4)
Where
M=(1+r)N. (5)

For efficiency purposes related to transmitter design, it is preferable that r is chosen so that M in equation (5) is an integer. Choosing r so that M is an integer allows for more efficient transmitters designs using, for example, Inverse Fast Fourier Transform (IFFT) techniques. Since M=N+N(r), and N is always an integer, this means that r must be chosen so that N(r) is an integer, Generally, it is preferable for r to be between 0.1 and 0.5. Therefore, if N is 16, for example, then 0.5 could be selected for r so that N(r) is an integer. Alternatively, if a value for r is chosen in the above example so that N(r) is not an integer, B can be made slightly wider than M/T to compensate. In this case, it is still preferable that r be chosen so that N(r) is approximately an integer.

2. Example Embodiment of a Wireless Communication System

With the above in mind,FIG. 6 illustrates anexample communication system600 comprising a plurality ofcells602 that each use a common wideband communication channel to communicate withcommunication devices604 within eachcell602. The common communication channel is a wideband communication channel as described above. Eachcommunication cell602 is defined as the coverage area of a base station, or service access point,606 within the cell. Onesuch base station606 is shown for illustration inFIG. 6. For purposes of this specification and the claims that follow, the term base station will be used generically to refer to a device that provides wireless access to the wireless communication system for a plurality of communication devices, whether the system is a line of sight, indoor, or outdoor system.

Because eachcell602 uses the same communication channel, signals in onecell602 must be distinguishable from signals inadjacent cells602. To differentiate signals from onecell602 to another,adjacent base stations606 use different synchronization codes according to a code reuse plan. InFIG. 6,system600 uses a synchronization code reuse factor of 4, although the reuse factor can vary depending on the application.

Preferably, the synchronization code is periodically inserted into a communication from abase station606 to acommunication device604 as illustrated inFIG. 7. After a predetermined number ofdata packets702, in this case two, theparticular synchronization code704 is inserted into the information being transmitted by eachbase station606. A synchronization code is a sequence of data bits known to both thebase station606 and anycommunication devices604 with which it is communicating. The synchronization code allows such acommunication device604 to synchronize its timing to that ofbase station606, which, in turn, allowsdevice604 to decode the data properly. Thus, in cell1 (see lightly shadedcells602 inFIG. 6), for example, synchronization code1 (SYNC1) is inserted intodata stream706, which is generated bybase station606 incell1, after every twopackets702; incell2 SYNC2 is inserted after every twopackets702; incell3 SYNC3 is inserted; and incell4 SYNC4 is inserted. Use of the synchronization codes is discussed in more detail below.

InFIG. 5A, an example wideband communication channel500 for use incommunication system600 is divided into 16sub-channels502, centered at frequencies f₀to f₁₅. Abase station606 at the center of eachcommunication cell602 transmits a single packet occupying the whole bandwidth B of wideband channel500. Such a packet is illustrated bypacket504 inFIG. 5B.Packet504 comprisessub-packets506 that are encoded with a frequency offset corresponding to one ofsub-channels502.Sub-packets506 in effect define available time slots inpacket504. Similarly, sub-channels502 can be said to define available frequency bins in communication channel500. Therefore, the resources available incommunication cell602 aretime slots506 andfrequency bins502, which can be assigned todifferent communication devices604 within eachcell602.

Thus, for example,frequency bins502 andtime slots506 can be assigned to 4different communication devices604 within acell602 as shown inFIG. 5. Eachcommunication device604 receives theentire packet504, but only processes thosefrequency bins502 and/ortimeslots506 that are assigned to it. Preferably, eachdevice604 is assignednon-adjacent frequency bins502, as inFIG. 5B. This way, if interference corrupts the information in a portion of communication channel500, then the effects are spread across alldevices604 within acell602. Hopefully, by spreading out the effects of interference in this manner the effects are minimized and the entire information sent to eachdevice604 can still be recreated from the unaffected information received in other frequency bins. For example, if interference, such as fading, corrupted the information in bins f₀-f₄, then each user 1-4 loses one packet of data. But each user potentially receives three unaffected packets from the other bins assigned to them. Hopefully, the unaffected data in the other three bins provides enough information to recreate the entire message for each user. Thus, frequency diversity can be achieved by assigning non-adjacent bins to each of multiple users.

Ensuring that the bins assigned to one user are separated by more than the coherence bandwidth ensures frequency diversity. As discussed above, the coherence bandwidth is approximately equal to 1/d_s. For outdoor systems, where d_sis typically 1 μs, 1/d_s=1/1 μs=1 MHz. Thus, the non-adjacent frequency bands assigned to a user are preferably separated by at least 1 MHz. It can be even more preferable, however, if the coherence bandwidth plus some guard band to ensure sufficient frequency diversity separate the non-adjacent bins assigned to each user. For example, it is preferable in certain implementations to ensure that at least 5 times the coherence bandwidth, or 5 MHz in the above example, separates the non-adjacent bins.

Another way to provide frequency diversity is to repeat blocks of data in frequency bins assigned to a particular user that are separated by more than the coherence bandwidth. In other words, if 4 sub-channels200 are assigned to a user, then data block a can be repeated in the first and third sub-channels200 and data block b can be repeated in the second andfourth sub-channels202, provided the. sub-channels are sufficiently separated in frequency. In this case, the system can be said to be using a diversity length factor of 2. The system can similarly be configured to implement other diversity lengths, e.g., 3, 4, . . . , l.

It should be noted that spatial diversity can also be included depending on the embodiment. Spatial diversity can comprise transmit spatial diversity, receive spatial diversity, or both. In transmit spatial diversity, the transmitter uses a plurality of separate transmitters and a plurality of separate antennas to transmit each message. In other words, each transmitter transmits the same message in parallel. The messages are then received from the transmitters and combined in the receiver. Because the parallel transmissions travel different paths, if one is affected by fading, the others will likely not be affected. Thus, when they are combined in the receiver, the message should be recoverable even if one or more of the other transmission paths experienced severe fading.

Receive spatial diversity uses a plurality of separate receivers and a plurality of separate antennas to receive a single message. If an adequate distance separates the antennas, then the transmission path for the signals received by the antennas will be different. Again, this difference in the transmission paths will provide imperviousness to fading when the signals from the receivers are combined.

Transmit and receive spatial diversity can also be combined within a system such assystem600 so that two antennas are used to transmit and two antennas are used to receive. Thus, eachbase station606 transmitter can include two antennas, for transmit spatial diversity, and eachcommunication device604 receiver can include two antennas, for receive spatial diversity. If only transmit spatial diversity is implemented insystem600, then it can be implemented inbase stations606 or incommunication devices604. Similarly, if only receive spatial diversity is included insystem600, then it can be implemented inbase stations606 orcommunication devices604.

The number ofcommunication devices604 assignedfrequency bins502 and/ortime slots506 in eachcell602 is preferably programmable in real time. La other words, the resource allocation within acommunication cell602 is preferably programmable in the face of varying external conditions, i.e.”, multipath or adjacent, cell interference, and varying requirements, i.e., bandwidth requirements for various users within the cell. Thus, ifuser1 requires the whole bandwidth to download a large video file, for example, then the allocation ofbins502 can be adjust to provideuser1 with more, or even all, ofbins502. Onceuser1 no longer requires such large amounts of bandwidth, the allocation ofbins502 can be readjusted among all of users1-4.

It should also be noted that all of the bins assigned to a particular user can be used for both the forward and reverse link. Alternatively, somebins502 can be assigned as the forward link and some can be assigned for use on the reverse link, depending on the implementation.

To increase capacity, the entire bandwidth B is preferably reused in eachcommunication cell602, with eachcell602 being differentiated by a unique synchronization code (see discussion below). Thus,system600 provides increased immunity to multipath and fading as well as increased band width due to the elimination of frequency reuse requirements.

3. Synchronization

FIG. 8 illustrates an example embodiment of asynchronization code correlator800. When adevice604 in cell1 (seeFIG. 6), for example, receives an incoming communication from thecell1

base station

606, it compares the incoming data with SYNC1 incorrelator800. Essentially, the device scans the incoming data trying to correlate the data with the known synchronization code, in this case SYNC1. Oncecorrelator800 matches the incoming data to SYNC1 it generates acorrelation peak804 at the output. Multipath versions of the data will also generatecorrelation peaks806, although thesepeaks806 are generally smaller thancorrelation peak804. The device can then use the correlation peaks to perform channel estimation, which allows the device to adjust for the multipath using, e.g., an equalizer. Thus, incell1, ifcorrelator800 receives a data stream comprising SYNC1, it will generate

correlation peaks

804 and806. If on the other hand, the data stream comprises SYNC2, for example, then no peaks will be generated and the device will essentially ignore the incoming communication.

Even though a data stream that comprises SYNC2 will not create any correlation peaks, it can create noise incorrelator800 that can prevent detection of correlation peaks804 and806. Several steps can be taken to prevent this from occurring. One way to minimize the noise created incorrelator800 by signals fromadjacent cells602, is to configuresystem600 so that eachbase station606 transmits at the same time. This way, the synchronization codes can preferably be generated in such a manner that only thesynchronization codes704 of adjacent cell data streams, e.g., streams708,710, and712, as opposed topackets702 within those streams, will interfere with detection of thecorrect synchronization code704, e.g., SYNC1. The synchronization codes can then be further configured to eliminate or reduce the interference.

For example, the noise or interference caused by an incorrect synchronization code is a function of the cross correlation of that synchronization code with respect to the correct code. The better the cross correlation between the two, the lower the noise level. When the cross correlation is ideal, then the noise level will be virtually zero as illustrated inFIG. 9 bynoise level902. Therefore, a preferred embodiment ofsystem600 uses synchronization codes that exhibit ideal cross correlation, i.e., zero. Preferably, the ideal cross correlation of the synchronization codes covers aperiod1 that is sufficient to allow accurate detection of multipath correlation peaks906 as well ascorrelation peak904. This is important so that accurate channel estimation and equalization can take place. Outside ofperiod1, thenoise level908 goes up, because the data inpackets702 is random and will exhibit low cross correlation with the synchronization code, e.g., SYNC1. Preferably,period1 is actually slightly longer then the multipath length in order to ensure that the multipath can be detected.

a. Synchronization Code Generation

Conventional systems use orthogonal codes to achieve cross correlation incorrelator800. Insystem600 for example, SYNC1, SYNC2, SYNC3, and SYNC4, corresponding to cells1-4 (see lightly shadedcells602 ofFIG. 6) respectively, will all need to be generated in such a manner that they will have ideal cross correlation with each other. In one embodiment, if the data streams involved comprise high and low data bits, then the value “1” can be assigned to the high data bits and “−1” to the low data bits. Orthogonal data sequences are then those that produce a “0” output when they are exclusively ORed (XORed) together incorrelator800. The following example illustrates this point fororthogonal sequences 1 and 2:


	sequence 1:	1 1 −1 1
	sequence 2:	1 1 1 −1
		1 1 −1 −1 = 0

Thus, when the results of XORing each bit pair are added, the result is “0.”

But insystem600, for example, each code must have ideal, or zero, cross correlation with each of the other codes used inadjacent cells602. Therefore, in one example embodiment of a method for generating synchronization codes exhibiting the properties described above, the process begins by selecting a “perfect sequence” to be used as the basis for the codes. A perfect sequence is one that when correlated with itself produces a number equal to the number of bits in the sequence. For example:


	Perfect sequence 1:	1 1 −1 1
		1 1 −1 1
		1 1 1 1 = 4

But each time a perfect sequence is cyclically shifted by one bit, the new sequence is orthogonal with the original sequence. Thus, for example, ifperfect sequence 1 is cyclically shifted by one bit and then correlated with the original, the correlation produces a “0” as in the following example:


	Perfect sequence 1:	1 1 −1 1
		1 1 1 −1
		1 1 −1 −1 = 0

If theperfect sequence 1 is again cyclically shifted by one bit, and again correlated with the original then it will produce a “0”. In general, you can cyclically shift a perfect sequence by any number of bits up to its length and correlate the shifted sequence with the original to obtain a “0”.

Once a perfect sequence of the correct length is selected, the first synchronization code is preferably generated in one embodiment by repeating thesequence 4 times. Thus, ifperfect sequence 1 is being used, then a first synchronization code y would be the following:

y=1 1-1111-1111-1111-1 1.

Or in generic form:

y=x(0)x(1)x(2)x(3)x(0)x(1)x(2)x(3)x(0)x(1)x(2)x(3)x(0)x(1)x(2)x(3).

For a sequence of length L:

y=x(0)x(1) . . . x(L)x(0)x(1) . . . x(L)x(0)x(1) . . . x(L)x(0)x(l) . . . x(L).

Repeating the perfect sequence allows correlator800 a better opportunity to detect the synchronization code and allows generation of other uncorrelated frequencies as well. Repeating has the effect of sampling in the frequency domain. This effect is illustrated by the graphs inFIG. 10. Thus, intrace1, which corresponds to synchronization code y, asample1002 is generated everyfourth sample bin1000. Each sample bin is separated by 1/(4L×T), where T is the symbol duration. Thus in the above example, where L=4, each sample bin is separated by 1/(16×T) in the frequency domain. Traces2-4 illustrate the next three synchronization codes. As can be seen, the samples for each subsequent synchronization code are shifted by one sample bin relative to the samples for the previous sequence. Therefore, none of sequences interfere with each other.

To generate the subsequent sequences, corresponding to traces2-4, sequence y must be shifted in frequency. This can be accomplished using the following equation:
z^r(m)=y(m)*exp(j*2*π*r*m/(n*L)), (5)

for r=1 to L (# of sequences) and m=0 to 4*L−1 (time); and

where: z^r(m)=each subsequent sequence,

y(m)=the first sequence, and

n=the number of times the sequence is repeated.

It will be understood that multiplying by an exp(j2π(r*m/N)) factor, where N is equal to the number of times the sequence is repeated (n) multiplied by the: length of the underlying perfect sequence L, in the time domain results in a shift in the frequency domain. Equation (5) results in the desired shift as illustrated inFIG. 10 for each of synchronization codes2-4, relative tosynchronization code1. The final step in generating each synchronization code is to append the copies of the last M samples, where M is the length of the multipath, to the front of each code. This is done to make the convolution with the multipath cyclic and to allow easier detection of the multipath.

It should be noted that synchronization codes can be generated from more than one perfect sequence using the same methodology. For example, a perfect sequence can be generated and repeated for times and then a second perfect sequence can be generated and repeated four times to get a n factor equal to eight. The resulting sequence can then be shifted as described above to create the synchronization codes.

b. Signal Measurements Using Synchronization Codes

Therefore, when a communication device is at the edge of a cell, it will receive signals from multiple base stations and, therefore, will be decoding several synchronization codes at the same time. This can be illustrated with the help ofFIG. 11, which illustrates another example embodiment of awireless communication system1100 comprising

communication cells

1102,1104, and1106 as well ascommunication device1108, which is in communication withbase station1110 ofcell1102 but also receiving communication from

base stations

1112 and1114 of

cells

1104 and1106, respectively.

If communications frombase station1110 comprise synchronization code SYNC1 and communications from

base station

1112 and1114 comprise SYNC2 and SYNC3 respectively, thendevice1108 will effectively receive the sum of these three synchronization codes. This is because, as explained above,

base stations

1110,1112, and1114 are configured to transmit at the same time. Also, the synchronization codes arrive atdevice1108 at almost the same time because they are generated in accordance with the description above.

Again as described above, the synchronization codes SYNC1, SYNC2, and SYNC3 exhibit ideal cross correlation. Therefore, whendevice1108 correlates the sum x of codes SYNC1, SYNC2, and SYNC3, the latter two will not interfere with proper detection of SYNC1 bydevice1108. Importantly, the sum x can also be used to determine important signal characteristics, because the sum x is equal to the sum of the synchronization code signal in accordance with the following equation:
x=SYNC1+SYNC2+SYNC3 (6)

Therefore, when SYNC1 is removed, the sum of SYNC2 and SYNC3 is left, as shown in the following:
x−SYNC1=SYNC2+SYNC3 (7)

The energy computed from the sum (SYNC2+SYNC3) is equal to the noise or interference seen bydevice1108. Since the purpose of correlating the synchronization code indevice1106 is to extract the energy in SYNC1,device1108 also has the energy in the signal frombase station1110, i.e., the energy represented by SYNC1 . Therefore,device1106 can use the energy of SYNC1 and of (SYNC2+SYNC3) to perform a signal-to-interference measurement for the communication channel over which it is communicating withbase station1110. The result of the measurement is preferably a signal-to-interference ratio (SIR). The SIR measurement can then be communicated back to base station.1110 for purposes that will be discussed below to perform extremely accurate determinations of the Channel Impulse Response (CIR), or channel estimation, from the correlation produced bycorrelator800. This allows for highly accurate equalization using low cost, low complexity equalizers, thus overcoming a significant draw back of conventional systems.

4. Sub-Channel Assignments

As mentioned, the SIR as determined bydevice1108 can be communicated back tobase station1110 for use in the assignment ofslots502. In one embodiment, due to the fact that each sub-channel502 is processed independently, the SIR for each sub-channel502 can be measured and communicated back tobase station1110. In such an embodiment therefore, sub-channels502 can be divided into groups and a SIR measurement for each group can be sent tobase station1110. This is illustrated inFIG. 12A, which shows awideband communication channel1200 segmented into sub-channels f₀to f₁₅. Sub-channels f₀to f₁₅are then grouped into 8 groups G1 to G8. Thus, in one embodiment,device1108 andbase station1110 communicate over a channel such aschannel1200.

Sub-channels in the same group are preferably separated by as many sub-channels as possible to ensure diversity. InFIG. 12A for example, sub-channels within the same group are 7 sub-channels apart, e.g., group G1 comprises f₀and f₈.

Device

1102 reports a SIR measurement for each of the groups G1 to G8. These SIR measurements are preferably compared with a threshold value to determine which sub-channels groups are useable bydevice1108. This comparison can occur indevice1108 orbase station1110. If it occurs indevice1108, thendevice1108 can simply report tobase station1110 which sub-channel groups are useable bydevice1108.

SIR reporting will be simultaneously occurring for a plurality of devices withincell1102. Thus,FIG. 12B illustrates the situation where two communication devices corresponding to user1 and user2 report SIR levels above the threshold for groups G1, G3, G5, and G7.Base station1110 preferably then assigns sub-channel groups to user1 and user2 based on the SIR reporting as illustrated inFIG. 12B. When assigning the “good” sub-channel groups to user1 and user2,base station1110 also preferably assigns them based on the principles of frequency diversity. InFIG. 12B, therefore, user1 and user2 are alternately assigned every other “good” sub-channel.

The assignment of sub-channels in the frequency domain is equivalent to the assignment of time slots in the time domain. Therefore, as illustrated inFIG. 13, two users, user1 and user2, receivepacket1302 transmitted overcommunication channel1200.FIG. 13 also illustrated the sub-channel assignment ofFIG. 12B. WhileFIG. 12 and13 illustrate sub-channel/time slot assignment based on SIR for two users, the principles illustrated can be extended for any number of users. Thus, a packet withincell1102 can be received by 3 or more users. Although, as the number of available sub-channels is reduced due to high SIR, so is the available bandwidth. In other words, as available sub-channels are reduced, the number of users that can gain access tocommunication channel1200 is also reduced.

Poor SIR can be caused for a variety of reasons, but frequently it results from a device at the edge of a cell receiving communication signals from adjacent cells. Because each cell is using the same bandwidth B, the adjacent cell signals will eventually raise the noise level and degrade SIR for certain sub-channels. In certain embodiments, therefore, sub-channel assignment can be coordinated between cells, such as

cells

1102,1104, and1106 inFIG. 11, in order to prevent interference from adjacent cells.

Thus, ifcommunication device1108 is near the edge ofcell1102, anddevice1118 is near the edge ofcell1106, then the two can interfere with each other. As a result, the SIR measurements that

device

1108 and1118 report back to

base stations

1110 and1114, respectively, will indicate that the interference level is too high.Base station1110 can then be configured to assign only the odd groups, i.e., G1, G3, G5, etc., todevice1108, whilebase station1114 can be configured to assign the even groups todevice1118 in- a coordinated fashion. The two

devices

1108 and1118 will then not interfere with each other due to the coordinated assignment of sub-channel groups.

Assigning the sub-channels in this manner reduces the overall bandwidth available to

devices

1108 and1118, respectively. La this case the bandwidth is reduced by a factor of two. But it should be remembered that devices operating closer to each

base station

1110 and1114, respectively, will still be able to use all sub-channels if needed. Thus, it is only devices, such asdevice1108, that are near the edge of a cell that will have the available bandwidth reduced. Contrast this with a CDMA system, for example, in which the bandwidth for all users is reduced, due to the spreading techniques used in such systems, by approximately a factor of 10 at all times. It can be seen, therefore, that the systems and methods for wireless communication over a wide bandwidth channel using a plurality of sub-channels not only improves the quality of service, but can also increase the available bandwidth significantly.

When there are three

devices

1108,1118, and1116 near the edge of their respective

adjacent cells

1102,1104, and1106, the sub-channels can be divided by three. Thus,device1108, for example, can be assigned groups G1, G4, etc.,device1118 can be assigned groups G2, G5, etc., anddevice1116 can be assigned groups G3, G6, etc. In this case the available bandwidth for these devices, i.e., devices near the edges of

cells

1102,1104, and1106, is reduced by a factor of 3, but this is still better than a CDMA system, for example.

The manner in which such a coordinated assignment of sub-channels can work is illustrated by the flow chart inFIG. 14. First instep1402, a communication device, such asdevice1108, reports the SIR for all sub-channel groups G1 to G8. The SIRs reported are then compared, instep1404, to a threshold to determine if the SIR is sufficiently low for each group. Alternatively,device1108 can make the determination and simply report which groups are above or below the SIR threshold. If the SIR levels are good for each group, then base station.1110 can make each group available todevice1108, instep1406. Periodically,device1108 preferably measures the SIR level andupdates base station1110 in case the SIR as deteriorated. For example,device1108 may move from near the center ofcell1102 toward the edge, where interference from an adjacent cell may affect the SIR fordevice1108.

If the comparison instep1404 reveals that the SIR levels are not good, thenbase station1110 can be preprogrammed to assign either the odd groups or the even groups only todevice1108, which it will do instep1408.Device1108 then reports the SIR measurements for the odd or even groups it is assigned instep1410, and they are again compared to a SIR threshold instep1412.

It is assumed that the poor SIR level is due to the fact thatdevice1108 is operating at the edge ofcell1102 and is therefore being interfered with by a device such asdevice1118. Butdevice1108 will be interfering withdevice1118 at the same time. Therefore, the assignment of odd or even groups instep1408 preferably corresponds with the assignment of the opposite groups todevice1118, bybase station1114. Accordingly, whendevice1108 reports the SIR measurements for whichever groups, odd or even, are assigned to it, the comparison instep1410 should reveal that the SIR levels are now below the threshold level. Thus,base station1110 makes the assigned groups available todevice1108 instep1414. Again,device1108 preferably periodically updates the SIR measurements by returning to step1402.

It is possible for the comparison ofstep1410 to reveal that the SIR levels are still above the threshold, which should indicate that a third device, e.g.,device1116 is still interfering withdevice1108. In this case,base station1110 can be preprogrammed to assign every third group todevice1108 instep1416. This should correspond with the corresponding assignments of non-interfering channels to

devices

1118 and1116 by

base stations

1114 and1112, respectively. Thus,device1108 should be able to operate on the sub-channel groups assigned, i.e., G1, G4, etc., without undue interference. Again,device1108 preferably periodically updates the SIR measurements by returning to step1402. Optionally, a third comparison step (not shown) can be implemented afterstep1416, to ensure that the groups assigned todevice1408 posses an adequate SIR level for proper operation. Moreover, if there are more adjacent cells, i.e., if it is possible for devices in a 4^thor even a 5^thadjacent cell to interfere withdevice1108, then the process ofFIG. 14 would continue and the sub-channel groups would be divided even further to ensure adequate SIR levels on the sub-channels assigned todevice1108.

Even though the process ofFIG. 14 reduces the bandwidth available to devices at the edge of

cells

1102,1104, and1106, the SIR measurements can be used in such a manner as to increase the data rate and therefore restore or even increase bandwidth. To accomplish this, the transmitters and receivers used in

base stations

1102,1104, and1106, and in devices in communication therewith, e.g.,

devices

1108,1114, and1116 respectively, must be capable of dynamically changing the symbol mapping schemes used for some or all of the sub-channel. For example, in some embodiments, the symbol mapping scheme can be dynamically changed among BPSK, QPSK, 8PSK, 16QAM, 32QAM, etc. As the symbol mapping scheme moves higher, i.e., toward 32QAM, the SIR level required for proper operation moves higher, i.e., less and less interference can be withstood. Therefore, once the SIR levels are determined for each group, the base station, e.g.,base station1110, can then determine what symbol mapping scheme can be supported for each sub-channel group and can change the modulation scheme accordingly.Device1108 must also change the symbol mapping scheme to correspond to that of the base stations. The change can be effected for all groups uniformly, or it can be effected for individual groups. Moreover, the symbol mapping scheme can be changed on just the forward link, just the reverse link, or both, depending on the embodiment.

Thus, by maintaining the capability to dynamically assign sub-channels and to dynamically change the symbol mapping scheme used for assigned sub-channels, the systems and methods described herein provide the ability to maintain higher available bandwidths with higher performance levels than conventional systems. To fully realize the benefits described, however, the systems and methods described thus far must be capable of implementation in a cost effect and convenient manner. Moreover, the implementation must include reconfigurability so that a single device can move between different types of communication described herein. The following descriptions detail example high level embodiments of hardware implementations configured to operate in accordance with the systems and methods described herein in such a manner as to provide the capability just described above.

5. Sample Transmitter Embodiments

FIG. 15 is logical block diagram illustrating an example embodiment of atransmitter1500 configured for wireless communication in accordance with the systems and methods described above. The transmitter could, for example be within a base station, e.g.,base station606, or within a communication device, such asdevice604,Transmitter1500 is provided to illustrate logical components that can be included in a transmitter configured in accordance with the systems and methods described herein. It is not intended to limit the systems and methods for wireless communication over a wide bandwidth channel using a plurality of sub-channels to any particular transmitter configuration or any particular wireless communication system.

With this in mind, it can be seen thattransmitter1500 comprises a serial-to-parallel converter1504 configured to receive aserial data stream1502 comprising a data rate R. Serial-to-parallel converter1504 convertsdata stream1502 into Nparallel data streams1520, where N is the number of sub-channels200. It should be noted that while the discussion that follows assumes that a single serial data stream is used, more than one serial data stream can also be used if required or desired. In any case, the data rate of eachparallel data stream1520 is then R/N. Eachdata stream1520 is then sent to a scrambler, encoder, andinterleaver block1506. Scrambling, encoding, and interleaving are common techniques implemented in many wireless communication transmitters and help to provide robust, secure communication. Examples of these techniques will be briefly explained for illustrative purposes.

Scrambling breaks on the data to be transmitted in an effort to smooth out the spectral density of the transmitted data. For example, if the data comprises a long string of “1”s, there will be a spike in the spectral density. This spike can cause greater interference within the wireless communication system. By breaking up the data, the spectral density can be smoothed out to avoid any such peaks. Often, scrambling is achieved by XORing the data with a random sequence,

Encoding, or coding, theparallel bit streams1520 can, for example, provide Forward Error Correction (FEC). The purpose of FEC is to improve the capacity of a communication channel by adding some, carefully designed redundant information to the data being transmitted through the channel. The process of adding this redundant information is known as channel coding. Convolutional coding and block coding are the two major forms of channel coding. Convolutional codes operate on serial data, one or a few bits at a time. Block codes operate on relatively large (typically, up to a couple of hundred bytes) message blocks. There are a variety of useful convolutional and block codes, and a variety of algorithms for decoding the received coded information sequences to recover the original data. For example, convolutional encoding or turbo, coding with Viterbi decoding is a FEC technique that is particularly suited to a channel in which the transmitted signal is corrupted mainly by additive white Gaussian noise (AWGN) or even a channel that simply experiences fading.

Convolutional codes are usually described using two parameters: the code rate convolutional encoder (k) to the number of channel symbols (n) output by the convolutional encoder in a given encoder cycle. A common code rate is ½, which means that 2 symbols are produced for every 1-bit input into the coder. The constraint length parameter, K, denotes the “length” of the convolutional encoder, i.e. how many k-bit stages are available to feed the combinatorial logic that produces the output symbols. Closely related to K is the parameter w, which indicates how many encoder cycles an input bit is retained and used for encoding after it first appears at the input to the convolutional encoder. The m parameter can be thought of as the memory length of the encoder.

Interleaving is used to reduce the effects of fading. Interleaving mixes up the order of the data so that if a fade interferes with a portion of the transmitted signal, the overall message will not be effected. This is because once the message is de-interleaved and decoded in the receiver, the data lost will comprise non-contiguous portions of the overall message. In other words, the fade will interfere with a contiguous portion of the interleaved message, but when the message is de-interleaved, the interfered with portion is spread throughout the overall message. Using techniques such as FEC, the missing information can then be filled in, or the impact of the lost data may just be negligible.

Afterblocks1506, eachparallel data stream1520 is sent tosymbol mappers1508.Symbol mappers1508 apply the requisite symbol mapping, e.g., BPSK, QPSK, etc., to eachparallel data stream1520.Symbol mappers1508 are preferably programmable so that the modulation applied to parallel data streams can be changed, for example, in response to the SIR reported for each sub-channel202. It is also preferable, that eachsymbol mapper1508 be separately programmable so that the optimum symbol mapping scheme for each sub-channel can be selected and applied to eachparallel data stream1520.

Aftersymbol mappers1508,parallel data streams1520 are sent tomodulators1510. Important aspects and features of example embodiments ofmodulators1510 are described below. After modulators1510,parallel data streams1520 are sent tosummer1512, which is configured to sum the parallel data streams and thereby generate a singleserial data stream1518 comprising each of the individually processed parallel data streams1520.Serial data stream1518 is then sent toradio transmitter1514, where it is modulated with an RF carrier, amplified, and transmitted viaantenna1516 according to known techniques. Radio module embodiments that can be used in conjunction with the systems and methods described herein are described below.

The transmitted signal occupies the entire bandwidth B ofcommunication channel100 and comprises each of the discreteparallel data streams1520 encoded onto theirrespective sub-channels102 within bandwidth B. Encodingparallel data streams1520 onto theappropriate sub-channels102 requires that eachparallel data stream1520 be shifted in frequency by an appropriate offset! This is achieved inmodulator1510.

FIG. 16 is a logical block diagram of an example embodiment of a modulator1600 in accordance with the systems and methods described herein. Importantly, modulator1600 takesparallel data streams1602 performs Time Division Modulation (TDM) or Frequency Division Modulation (FDM) on eachdata stream1602, filters them usingfilters1612, and then shifts each data stream in frequency usingfrequency shifter1614 so that they occupy the appropriate sub-channel.Filters1612 apply the required pulse snapping, i.e., they apply the roll-off factor described insection 1. The frequency shiftedparallel data streams1602 are then summed and transmitted. Modulator1600 can also includerate controller1604,frequency encoder1606, andinterpolators1610. All of the components shown inFIG. 16 are described in more detail in the following paragraphs and in conjunction withFIGS. 17-23.

FIG. 17 illustrates one example embodiment of arate controller1700 in accordance with the systems and methods described herein.Rate control1700 is used to control the data rate of eachparallel data stream1602. Inrate controller1700, the data rate is halved by repeating data streams d(0) to d(7), for example, producing streams a(0) to a(15) in which a(0) is the same as a(8), a(1) is the same as a(9), etc.FIG. 17 illustrates that the effect of repeating the data streams in this manner is to take the data streams that are encoded onto the first 8 sub-channels1702, and duplicate them on the next 8 sub-channels1702. As can be seen 7 sub-channels separate sub-channels1702 comprising the same, or duplicate, data streams. Thus, if fading effects one sub-channel1702, for example, the other sub-channels1702 carrying the same data will likely not be effected, i.e., there is frequency diversity between the duplicate data streams. So by sacrificing data rate, in this case half the data rate, more robust transmission is achieved. Moreover, the robustness provided by duplicating the data streams d(0) to d(8) can be further enhanced by applying scrambling to the duplicated data streams via scramblers1704.

It should be noted that the data rate can be reduced by more than half, e.g., by four or more. Alternatively, the data rate can also be reduced by an amount other than half. For example if information from n data stream is encoded onto m sub-channels, where m>n. Thus, to decrease the rate by ⅔, information from one data stream can be encoded on a first sub-channel, information from a second data stream can be encoded on a second data channel, and the sum or difference of the two data streams can be encoded on a third channel. In which case, proper scaling will need to be applied to the power in the third channel. Otherwise, for example, the power in the third channel can be twice the power in the first two.

Preferably,rate controller1700 is programmable so that the data rate can be changed responsive to certain operational factors. For example, if the SIR reported for sub-channels1702 is low, thenrate controller1700 can be programmed to provide more robust transmission via repetition to ensure that no data is lost due to interference. Additionally, different types of wireless communication system, e.g., indoor, outdoor, line-of-sight, may require varying degrees of robustness. Thus,rate controller1700 can be adjusted to provide the minimum required robustness for the particular type of communication system. This type of programmability not only ensures robust communication, it can also be used to allow a single device to move between communication systems and maintain superior performance.

FIG. 18 illustrates an alternative example embodiment of arate controller1800 in accordance with the systems and methods described. Inrate controller1800 the data rate is increased instead of decreased. This is accomplished using serial-to-parallel converters1802 to convert each data streams d(0) to d(15), for example, into two data streams.Delay circuits1804 then delay one of the two data streams generated by each serial-to-parallel converter1802 by ½ a symbol, period. Thus, data streams d(0) to d(15) are transformed into data streams a(0) to a(31). The data streams generated by a particular serial-to-parallel converter1802 andassociate delay circuit1804 must then be summed and encoded onto the appropriate sub-channel. For example, data streams a(0) and a(1) must be summed and encoded onto the first sub-channel. Preferably, the data streams are summed subsequent to each data stream being pulsed shaped by afilter1612.

Thus,rate controller1604 is preferably programmable so that the data rate can be increased, as inrate controller1800, or decreased, as inrate controller1700, as required by a particular type of wireless communication system, or as required by the communication channel conditions or sub-channel conditions. In the event that the data rate is increased,filters1612 are also preferably programmable so that they can be configured to apply pulse shaping to data streams a(0) to a(31), for example, and then sum the appropriate streams to generate the appropriate number of parallel data streams to send tofrequency shifter1614.

The advantage of increasing the data rate in the manner illustrated inFIG. 18 is that higher symbol mapping rates can essentially be achieved, without changing the symbol mapping used insymbol mappers1508. Once the data streams are summed, the summed streams are shifted in frequency so that they reside in the appropriate sub-channel. But because the number of bits per each symbol has been doubled, the symbol mapping rate has been doubled. Thus, for example, a 4QAM symbol mapping can be converted to a 16QAM symbol mapping, even if the SIR is too high for 16QAM symbol mapping to otherwise be applied. In other words,programming rate controller1800 to increase the data rate in the manner illustrated inFIG. 18 can increase the symbol mapping even when channel conditions would otherwise not allow it, which in turn can allow a communication device to maintain adequate or even superior performance regardless of the type of communication system.

The draw back to increasing the data rate as illustrated inFIG. 18 is that interference is increased, as is receiver complexity. The former is due to the increased amount of data, the latter is due to the fact that each symbol cannot be processed independently because of the ½ symbol overlap. Thus, these concerns must be balanced against the increase symbol mapping ability when implementing a rate controller such asrate controller1800.

FIG. 19 illustrates one example embodiment of afrequency encoder1900 in accordance with the systems and methods described herein. Similar to rate encoding, frequency encoding is preferably used to provide increased communication robustness. Infrequency encoder1900 the sum or difference of multiple data streams are encoded onto each sub-channel. This is accomplished usingadders1902 to sum data streams d(0) to d(7) with data streams d(8) to d(15), respectively, whileadders1904 subtract data streams d(0) to d(7) from data streams d(8) to d(15), respectively, as shown. Thus, data streams a(0) to a(15) generated by

adders

1902 and1904 comprise information related to more than one data streams d(0) to d(15). For example, a(0) comprises the sum of d(0) and d(8), i.e., d(0)+d(8), while a(8) comprises d(8)−d(0). Therefore, if either a(0) or a(8) is not received due to fading, for example, then both of data streams d(0) and d(8) can still be retrieved from data stream a(8).

Essentially, the relationship between data stream d(0) to d(15) and a(0) to a(15) is a matrix relationship. Thus, if the receiver knows the correct matrix to apply, it can recover the sums and differences of d(0) to d(15) from a(0) to a(15). Preferably,frequency encoder1900 is programmable, so that it can be enabled and disabled in order to provided robustness when required. Preferable,

adders

1902 and1904 are programmable also so that different matrices can be applied to d(0) to d(15).

After frequency encoding, if it is included,data streams1602 are sent to TDM/FDM blocks1608. TDM/FDM blocks1608 perform TDM or FDM on the data streams as required by the particular embodiment.FIG. 20 illustrates an example embodiment of a TDM/FDM block2000 configured to perform TDM on a data stream. TDM/FDM block2000 is provided to illustrate the logical components that can be included in a TDM/FDM block configured to perform TDM on a data stream. Depending on the actual implementation, some of the logical components may or may not be included. TDM/FDM block2000 comprises asub-block repeater2002, asub-block scrambler2004, asub-block terminator2006, asub-block repeater2008, and aSYNC inserter2010.

Sub-block repeater

2002 is configured to receive a sub-block of data, such asblock2012 comprising bits a(0) to a(3) for example. Sub-block repeater is then configured to repeatblock2012 to provide repetition, which in turn leads to more robust communication. Thus,sub-block repeater2002 generatesblock2014, which comprises 2blocks2012.Sub-block scrambler2004 is then configured to receiveblock2014 and to scramble it, thus generatingblock2016. One method of scrambling can be to invert half ofblock2014 as illustrated inblock2016. But other scrambling methods can also be implemented depending on the embodiment.

Sub-block terminator

2006 takesblock2016 generated bysub-block scrambler2004 and adds atermination block2034 to the front ofblock2016 to formblock2018.Termination block2034 ensures that each block can be processed independently in the receiver. Withouttermination block2034, some blocks may be delayed due to multipath, for example, and they would therefore overlap part of the next block of data. But by includingtermination block2034, the delayed block can be prevented from overlapping any of the actual data in the next block.

Termination block

2034 can be acyclic prefix termination2036. Acyclic prefix termination2036 simply repeats the last few symbols ofblock2018. Thus, for example, ifcyclic prefix termination2036 is three symbols long, then it would simply repeat the last three symbols ofblock2018. Alternatively,termination block2034 can comprise a sequence of symbols that are known to both the transmitter and receiver. The selection of what type ofblock termination2034 to use can impact what type of equalizer is used in the receiver. Therefore, receiver complexity and choice of equalizers must be considered when determining what type oftermination block2034 to use in TDM/FDM block2000.

Aftersub-block terminator2006, TDM/FDM block2000 can include asub-block repeater2008 configured to perform a second block repetition step in which block2018 is repeated to formblock2020. In certain embodiments, sub-block repeater can be configured to perform a second block scrambling step as well. Aftersub-block repeater2008, if included, TDM/FDM block2000 comprises a SYNC inserter210 configured to periodically insert anappropriate synchronization code2032 after a predetermined number ofblocks2020 and/or to insert known symbols into each block. The purpose ofsynchronization code2032 is discussed in sections.

FIG. 21, on the other hand, illustrates an example embodiment of a TDM/FDM block2100 configured for FDM, which comprisessub-block repeater2102,sub-block scrambler2104,block coder2106,sub-block transformer2108,sub-block terminator2110, andSYNC inserter2112.Sub-block repeater2102 repeatsblock2114 and generatesblock2116. Sub-block scrambler then scramblesblock2116, generatingblock2118.Sub-block coder2106 takes block generates symbols b. This requires joint demodulation in the receiver, which is more robust but also more complex.Sub-block transformer2108 then performs a transformation onblock2120, generatingblock2122. Preferably, the transformation is an IFFT ofblock2120, which allows for more efficient equalizers to be used in the receiver. Next,sub-block terminator2110 terminatesblock2122, generatingblock2124 andSYNC inserter2112 periodically inserts asynchronization code2126 after a certain number ofblocks2124 and/or insert known symbols into each block. Preferably,sub-block terminator2110 only uses cyclic prefix termination as described above. Again this allows for more efficient receiver designs.

TDM/FDM block2100 is provided to illustrate the logical components that can be included in a TDM/FDM block configured to perform FDM on a data stream. Depending on the actual implementation, some of the logical components may or may not be included. Moreover, TDM/

FDM block

2000 and2100 are preferably programmable so that the appropriate logical components can be included as required by a particular implementation. This allows a device that incorporates one of

blocks

2000 or2100 to move between different systems with different requirements. Further, it is preferable that TDM/FDM block1608 inFIG. 16 be programmable so that it can be programmed to perform TDM, such as described in conjunction withblock2000, or FDM, such as described in conjunction withblock2100, as required by a particular communication system.

After TDM/FDM blocks1608, inFIG. 16, the parallel data streams are preferably passed tointerpolators1610.

Afterinterpolators1610, the parallel data streams are passed tofilters1612, which apply the pulse shaping described m conjunction with the roll-off factor of equation (2) insection 1. Then the parallel data streams are sent tofrequency shifter1614, which is configured to shift each parallel data stream by the frequency offset associated with the sub-channel to which the particular parallel data stream is associated.

FIG. 22 illustrates an example embodiment of afrequency shifter2200 in accordance with the systems and methods described herein. As can be seen,frequency shifter2200 comprisesmultipliers2202 configured to multiply each parallel data stream by the appropriate exponential to achieve the required frequency shift. Each exponential is of the form: exp(j2πf_cnT/rM), where c is the corresponding sub-channel, e.g., c=0 to N−1, and n is time. Preferably,frequency shifter1614 inFIG. 16 is programmable so that various channel/sub-channel configurations can be accommodated for various different systems. Alternatively, an IFFT block can replaceshifter1614 and filtering can be done after the IFFT block. This type of implementation can be more efficient depending on the implementation.

After the parallel data streams are shifted, they are summed, e.g., insummer1512 ofFIG. 15. The summed data stream is then transmitted using the entire bandwidth B of the communication channel being used. But the transmitted data stream also comprises each of the parallel data streams shifted in frequency such that they occupy the appropriate sub-channel. Thus, each sub-channel may be assigned to one user, or each sub-channel may carry a data stream intended for different users. The assignment of sub-channels is described in section 3b. Regardless of how the sub-channels are assigned, however, each user will receive the entire bandwidth, comprising all the sub-channels, but will only decode those sub-channels assigned to the user.

6. Sample Receiver Embodiments

FIG. 23 illustrates an example embodiment of areceiver2300 that can be configured in accordance with the present invention.Receiver2300 comprises anantenna2302 configured to receive a message transmitted by a transmitter, such astransmitter1500. Thus,antenna2302 is configured to receive a wide band message comprising the entire bandwidth B of a wide band channel that is divided into sub-channels of bandwidth B. As described above, the wide band message comprises a plurality of messages each encoded onto each of a corresponding sub-channel. All of the sub-channels may or may not be assigned to a device that includesreceiver2300; therefore,receiver2300 may or may not be required to decode all of the sub-channels,

After the message is received byantenna2300, it is sent toradio receiver2304, which is configured to remove the carrier associated with the wide band communication channel and extract a baseband signal comprising the data stream transmitted by the transmitter. Example radio receiver embodiments are described in more detail below.

The baseband signal is then sent tocorrelator2306 anddemodulator2308.Correlator2306 is configured to correlated with a synchronization code inserted in the data stream as described insection 3. It is also preferably configured to perform SIR and multipath estimations as described in section 3(b).Demodulator2308 is configured to extract the parallel data streams from each sub-channel assigned to thedevice comprising receiver2300 and to generate a single data stream therefrom.

FIG. 24 illustrates an example embodiment of ademodulator2400 in accordance with the systems and methods described herein.Demodulator2400 comprises afrequency shifter2402, which is configured to apply a frequency offset to the baseband data stream so that parallel data streams comprising the baseband data stream can be independently processed inreceiver2300. Thus, the output offrequency shifter2402 is a plurality of parallel data streams, which are then preferably filtered byfilters2404.Filters2404 apply a filter to each parallel data stream that corresponds to the pulse shape applied in the transmitter, e.g.,transmitter1500. Alternatively, an FFT block can replaceshifter2402 and filtering can be done after the FFT block. This type of implementation can be more efficient depending on the implementation.

Next,demodulator2400 preferably includesdecimators2406 configured to decimate the data rate of the parallel bit streams. Sampling at higher rates helps to ensure accurate recreation of the data. But the higher the data rate, the larger and morecomplex equalizer2408 becomes. Thus, the sampling rate, and therefore the number of samples, can be reduced bydecimators2406 to an adequate level that allows for a smaller and lesscostly equalizer2408.

Equalizer

2408 is configured to reduce the effects of multipath inreceiver2300. Its operation will be discussed more fully below. Afterequalizer2408, the parallel data streams are sent to de-scrambler, decoder, and de-interleaver2410, which perform the opposite operations of scrambler, encoder, andinterleaver1506 so as to reproduce the original data generated in the transmitter. The parallel data streams are then sent to parallel toserial converter2412, which generates a single serial data stream from the parallel data streams.

Equalizer

2408 uses the multipath estimates provided bycorrelator2306 to equalize the effects of multipath inreceiver2300. In one embodiment,equalizer2408 comprises Single-La Single-Out (SISO) equalizers operating on each parallel data stream indemodulator2400. In this case, each SISOequalizer comprising equalizer2408 receives a single input and generates a single equalized output. Alternatively, each equalizer can be a Multiple-In Multiple-Out (MIMO) or a Multiple-In Single-Out (MISO) equalizer. Multiple inputs can be required for example, when a frequency encoder or rate controller, such asfrequency encoder1900, is included in the transmitter. Becausefrequency encoder1900 encodes information from more than one parallel data stream onto each sub-channel, eachequalizers comprising equalizer2408 need to equalize more than one sub-channel. Thus, for example, if a parallel data stream indemodulator2400 comprises d(1) +d(8), thenequalizer2408 will need to equalize both d(1) and d(8) together.Equalizer2408 can then generate a single output corresponding to d(1) or d(8) (MISO) or it can generate both d(1) and d(8) (MIMO).

Equalizer

2408 can also be a time domain equalizer (TDE) or a frequency domain equalizer (FDE) depending on the embodiment. Generally,equalizer2408 is a TDE if the modulator in the transmitter performs TDM on the parallel data streams, and a FDE if the modulator performs FDM. Butequalizer2408 can be an FDE even if TDM is used in the transmitter. Therefore, the preferred equalizer type should be taken into consideration when deciding what type of block termination to use in the transmitter. Because of power requirements, it is often preferable to use FDM on the forward link and TDM on the reverse link in a wireless communication system.

As withtransmitter1500, the variouscomponents comprising demodulator2400 are preferably programmable, so that a single device can operate in a plurality of different systems and still maintain superior performance, which is a primary advantage of the systems and methods described herein. Accordingly, the above discussion provides systems and methods for implementing a channel access protocol that allows the transmitter and receiver hardware to be reprogrammed slightly depending on the communication system.

Thus, when a device moves from one system to another, it preferably reconfigures the hardware, i.e. transmitter and receiver, as required and switches to a protocol stack corresponding to the new system. An important part of reconfiguring the receiver is reconfiguring, or programming, the equalizer because multipath is a main problem for each type of system. The multipath, however, varies depending on the type of system, which previously has meant that a different equalizer is required for different types of communication systems. The channel access protocol described in the preceding sections, however, allows for equalizers to be used that need only be reconfigured slightly for operation in various systems.

a. Sample Equalizer Embodiment

FIG. 25 illustrates an example embodiment of areceiver2500 illustrating one way to configureequalizers2506 in accordance with the systems and methods described herein. Before discussing the configuration ofreceiver2500, it should be noted that one way to configureequalizers2506 is to simply include one equalizer per channel (for the systems and methods described herein, a channel is the equivalent of a sub-channel as described above). A correlator, such as correlator2306 (FIG. 23), can then provideequalizers2506 with an estimate of the number, amplitude, and phase of any multipaths present, up to some maximum number. This is also known as the Channel Impulse Response (CIR). The maximum number of multipaths is determined based on design criteria for a particular implementation. The more multipaths included in the CIR the more path diversity the receiver has and the more robust communication in the system will be. Path diversity is discussed a little more fully below.

If there is oneequalizer2506 per channel, the CIR is preferably provided directly toequalizers2506 from the correlator (not shown). If such a correlator configuration is used, thenequalizers2506 can be run at a slow rate, but the overall equalization process is relatively fast. For systems with a relatively small number of channels, such a configuration is therefore preferable. The problem, however, is that there is large variances in the number of channels used in different types of communication systems. For example, an outdoor system can have has many as 256 channels. This would require 256equalizers2506, which would make the receiver design too complex and costly. Thus, for systems with a lot of channels, the configuration illustrated inFIG. 25 is preferable. Inreceiver2500, multiple channels share eachequalizer2506. For example, each equalizer can be shared by 4 channels, e.g., CH1-Ch4, Ch5-CH8, etc., as illustrated inFIG. 25. In which case,receiver2500 preferably comprises amemory2502 configured to store information arriving on each channel.

Memory

2502 is preferably divided intosub-sections2504, which are each configured to store information for a particular subset of channels. Information for each channel in each subset is then alternately sent to theappropriate equalizer2506, which equalizes the information based on the CIR provided for that channel. In this case, each equalizer must run much faster than it would if there was simply one equalizer per channel. For example,equalizers2506 would need to run 4 or more times as fast in order to effectively equalize 4 channels as opposed to 1. In addition,extra memory2502 is required to buffer the channel information. But overall, the complexity ofreceiver2500 is reduced, because there are fewer equalizers. This should also lower the overall cost to implementreceiver2500.

Preferably,memory2502 and the number of channels that are sent to a particular equalizer is programmable. In this way,receiver2500 can be reconfigured for the most optimum operation for a given system. Thus, ifreceiver2500 were moved from an outdoor system to an indoor system with fewer channels, thenreceiver2500 can preferably be reconfigured so that there are fewer, even as few as 1, channel per equalizer. The rate at whichequalizers2506 are run is also preferably programmable such thatequalizers2506 can be run at the optimum rate for the number of channels being equalized.

In addition, if eachequalizer2506 is equalizing multiple channels, then the CIR for those multiple paths must alternately be provided to eachequalizer2506. Preferably, therefore, a memory (not shown) is also included to buffer the CIR information for each channel. The appropriate CIR information is then sent to each equalizer from the CIR memory (not shown) when the corresponding channel information is being equalized. The CIR memory (not shown) is also preferably programmable to ensure optimum operation regardless of what type ofsystem receiver2500 is operating in.

Returning to the issue of path diversity, the number of paths used byequalizers2506 must account for the delay spread d_sin the system. For example, if the system is an outdoor system operating in the 5 GHz range, the communication channel can comprise a bandwidth of 125 MHz, e.g., the channel can extend from 5.725 GHz to 5.85 GHz. If the channel is divided into 512 sub-channels with a roll-off factor r of 0.125, then each sub-channel will have a bandwidth of approximately 215 KHz, which provides approximately a 4.6 μs symbol duration. Since the worst case delay spread d_sis 20 μs, the number of paths used byequalizers2504 can be set to a maximum of 5. Thus, there would be a first path PI at 0 μs, a second path P2 at 4.6 μs, a third path P3 at 9.2 μs, a fourth path P4 at 13.8 μs, and fifth path P5 at 18.4 μs as, which is close to the delay spread d_s.

In another embodiment, a sixth path can be included so as to completely cover the delay spread d_s; however, 20 μs is the worst case. In fact, a delay spread d_sof 3 μs is a more typical value. In most instances, therefore, the delay spread d_swill actually be shorter and an extra path is not needed. Alternatively, fewer sub-channels can be used, thus providing a larger symbol duration, instead of using an extra path. But again, this would typically not be needed.

As explained above,equalizers2506 are preferably configurable so that they can be reconfigured for various communication systems. Thus, for example, the number of paths used must be sufficient regardless of the type of communication system. But this is also dependent on the number of sub-channels used. If, for example,receiver2500 went from operating in the above described outdoor system to an indoor system, where the delay spread d_sis on the order of 1 μs, thenreceiver2500 can preferably be reconfigured for 32 sub-channels and 5 paths. Assuming the same overall bandwidth of 125 MHz, the bandwidth of each sub-channel is approximately 4 MHz and the symbol duration is approximately 250 ns.

Therefore, there will be a first path PI at 0 μs and subsequent paths P2 to P5 at 250 ns, 500 ns, 750 ns, and 1 μs, respectively. Thus, the delay spread d_sshould be covered for the indoor environment. Again, the 1 μs d_sis worst case so the 1 μs d_sprovided in the above example will often be more than is actually required. This is preferable, however, for indoor systems, because it can allow operation to extend outside of the inside environment, e.g., just outside the building in which the inside environment operates. For campus style environments, where a user is likely to be traveling between buildings, this can be advantageous.

7. Sample Embodiment of a Wireless Communication Device

FIG. 26 illustrates an example embodiment of a wireless communication device in accordance with the systems and methods described herein. Device2600 is, for example, a portable communication device configured for operation in a plurality of indoor and outdoor communication systems. Thus, device2600 comprises anantenna2602 for transmitting and receiving wireless communication signals over awireless communication channel2618.Duplexer2604, or switch, can be included so thattransmitter2606 andreceiver2608 can both useantenna2602, while being isolated from each other. Duplexers, or switches used for this purpose, are well known and will not be explained herein.

Transmitter

2606 is a configurable- transmitter configured to implement the channel access protocol described above. Thus,transmitter2606 is capable of transmitting and encoding a wideband communication signal comprising a plurality of sub-channels. Moreover,transmitter2606 is configured such that the various subcomponents that comprisetransmitter2606 can be reconfigured, or programmed, as described insection 5. Similarly,receiver2608 is configured to implement the channel access protocol described above and is, therefore, also configured such that the varioussub-components comprising receiver2608 can be reconfigured, or reprogrammed, as described insection 6.

Transmitter

2606 andreceiver2608 are interfaced withprocessor2610, which can comprise various processing, controller, and/or Digital Signal Processing (DSP) circuits.Processor2610 controls the operation of device2600 including encoding signals to be transmitted bytransmitter2606 and decoding signals received byreceiver2608.Device2610 can also includememory2612, which can be configured to store operating instructions, e.g., firmware/software, used byprocessor2610 to control the operation of device2600.

Processor

2610 is also preferably configured to reprogramtransmitter2606 andreceiver2608 via

control interfaces

2614 and2616, respectively, as required by the wireless, communication system in which device2600 is operating. Thus, for example, device2600 can be configured to periodically ascertain the availability is a preferred communication system. If the system is detected, thenprocessor2610 can be configured to load the corresponding operating instruction frommemory2612 and reconfiguretransmitter2606 andreceiver2608 for operation in the preferred system.

For example, it may preferable for device2600 to switch to an indoor wireless LAN if it is available. So device2600 may be operating in a wireless WAN where no wireless LAN is available, while periodically searching for the availability of an appropriate wireless LAN. Once the wireless LAN is detected,processor2610 will load the operating instructions, e.g., the appropriate protocol stack, for the wireless LAN environment and will reprogramtransmitter2606 andreceiver2608 accordingly. In this manner, device2600 can move from one type of communication system to another, while maintaining superior performance.

It should be noted that a base station configured in accordance with the systems and methods herein will operate in a similar manner as device2600; however, because the base station does not move from one type of system to another, there is generally no need to configureprocessor2610 to reconfiguretransmitter2606 andreceiver2608 for operation in accordance with the operating instruction for a different type of system. Butprocessor2610 can still be configured to reconfigure, or reprogram the sub-components oftransmitter2606 and/orreceiver2608 as required: by the operating conditions within the system as reported by communication devices in communication with the base station. Moreover, such a base station can be configured in accordance with the systems and methods described herein to implement more than one mode of operation. In which case,controller2610 can be configured to reprogramtransmitter2606 andreceiver2608 to implement the appropriate mode of operation.

8. Bandwidth Recovery

As described above in relation toFIGS. 11-14, when a device, such asdevice1118 is near the edge of acommunication cell1106, it may experience interference frombase station1112 of anadjacent communication cell1104. In this case,device1118 will report a low SIR tobase station1114, which will causebase station1114 to reduce the number of sub-channels assigned todevice1118. As explained in relation toFIGS. 12 and 13, this reduction can comprisebase station1114 assigning only even sub-channels todevice1118. Preferably,base station1112 is correspondingly assigning only odd sub-channels todevice1116.

In this manner,

base station

1112 and1114 perform complementary reductions in the channels assigned to

devices

1116 and1118 in order to prevent interference and improve performance of

devices

1116 and1118. The reduction in assigned channels reduces the overall bandwidth available to

devices

1116 and1118. But as described above, a system implementing such a complementary reduction of sub-channels will still maintain a higher bandwidth than conventional systems. Still, it is preferable to recover the unused sub-channels, or unused bandwidth, created by the reduction of sub-channels in response to a low reported SIR.

One method for recovering the unused bandwidth is illustrated in the flow chart ofFIG. 27. First, instep2702,base station1114 receives SIR reports for different groups of sub-channels fromdevice1118 as described above. If the group SIR reports are good, thenbase station1114 can assign all sub-channels todevice1118 instep2704. If, however, some of the group SIR reports received instep2702 are poor, thenbase station1114 can reduce the number of sub-channels assigned todevice1118, e.g., by assigning only even sub-channels, instep2706. At the same time,base station1112 is preferably performing a complementary reduction in the sub-channels assigned todevice1116, e.g., by assigning only odd sub-channels.

At this point, each base station has unused bandwidth with respect to

devices

1116 and1118. To recover this bandwidth,base station1114 can, instep2708, assign the unused odd sub-channels todevice1116 inadjacent ceil1104. It should be noted that even though

cells

1102,1104, and1106 are illustrated as geometrically shaped, non-overlapping coverage areas, the actual coverage areas do not resemble these shapes. The shapes are essentially fictions used to plan and describe awireless communication system1100. Therefore,base station1114 can in fact communicate withdevice1116, even though it is inadjacent cell1104.

Oncebase station1114 has assigned the odd sub-channels todevice1116, in step2708.,

base station

1112 and1114 communicate withdevice1116 simultaneously over the odd sub-channels instep2710. Preferably,base station1112 also assigns the unused even sub-channels todevice1118 in order to recover the unused bandwidth incell1104 as well.

In essence, spatial diversity is achieved by having both

base station

1114 and1112 communicate with device1116 (and1118) over the same sub-channels. Spatial diversity occurs when the same message is transmitted simultaneously over statistically independent communication paths to the same receiver. The independence of the two paths improves the overall immunity of the system to fading. This is because the two paths will experience different fading effects. Therefore, if the receiver cannot receive the signal over one path due to fading, then it will probably still be able to receive the signal over the other path, because the fading that effected the first path will not effect the second. As a result, spatial diversity improves overall system performance by improving the Bit Error Rate (BER) in the receiver, which effectively increases the deliverable data rate to the receiver, i.e., increase the bandwidth.

For effective spatial diversity,

base stations

1112 and1114 ideally transmit the same information at the same time over the same sub-channels. As mentioned above, each base station insystem1100 is configured to transmit simultaneously, i.e.,system1100 is a TDM system with synchronized base stations.Base stations1112 and1114-also assigned the same sub-channels todevice1116 instep2708. Therefore, all that is left is to ensure that

base stations

1112 and1114 send the same information. Accordingly, the information communicated todevice1116 by

base stations

1112 and1114 is preferably coordinated so that the same information is transmitted at the same time. The mechanism for enabling this coordination is discussed more fully below. Such coordination, however, also allows encoding that can provide further performance enhancements withinsystem1100 and allow a greater percentage of the unused bandwidth to be recovered.

One example coordinated encoding scheme that can be implemented between

base stations

1112 and1114 with respect to communications withdevice1116 is Space-Time-Coding (ST.C) diversity. STC is illustrated bysystem2800 inFIG. 28. Insystem2800,transmitter2802 transmits a message overchannel2808 toreceiver2806. Simultaneously,transmitter2804 transmits a message overchannel2810 toreceiver2806. Because

channels

2808 and2810 are independent,system2800 will have spatial diversity with respect to communications from

transmitters

2802 and2804 toreceiver2806. In addition, however, the data transmitted by each

transmitter

2802 and2804 can be encoded to also provide time diversity. The following equations illustrate the process of encoding and decoding data in a STC system, such assystem2800.

First,channel2808 can be denoted hn andchannel2810 can be denoted gn, where:
h_n=a_he^jθh; and (1)
g_n=a_ge^jθg, (2)

Second, we can look at two blocks of

data

2812aand2812bto be transmitted bytransmitter2802 as illustrated inFIG. 28.Block2812acomprises N-symbols denoted as a₀, a₁, a₂, . . . , a_N-1, or a(0:N−1).Block2812btransmits N-symbols of data denoted b(0: N−1).Transmitter2804 simultaneously transmits two block of

data

2814aand2814b.Block2814ais the negative inverse conjugate ofblock2812band can therefore be described as −b*(N−1:0).Block2814bis the inverse conjugate ofblock2812aand can therefore be described as a*(N−1:0). It should be noted that each block of data in the forgoing description will preferably comprise a cyclical prefix as described above.

When blocks2812a,2812b,2814a, and2814bare received inreceiver2806, they are combined and decoded in the following manner: First, the blocks will be combined in the receiver to form the following blocks, after discarding the cyclical prefix:
Block1=a(0:N−1){circle around (×)}h_n−b*(N−1:0){circle around (×)}g_n; and (3)
Block2=b(0:−N−1){circle around (×)}h_n+a*(N−1:0){circle around (×)}g_n. (4)

Where the symbol {circle around (×)} represents a cyclic convolution.

Second, by taking an IFFT of the blocks, the blocks can be described as:
Block1=A_n*H_n−B_n**G_n; and (5)
Block2=B_n*H_n−A_n**G_n. (6)

Where n=0 toN−1.

In equations (5) and (6) H_nand G_nwill be known, or can be estimated. But to solve the two equations and determine A_nand B_n,it is preferable to turn equations (5) and (6) into two equations with two unknowns. This can be achieved using estimated signals X_nand Y_nas follows:
X_n=A_n*H_n−B_n**G_n; and (7)
Y_n=B_n*H_n+A_n**G_n. (8)

To generate two equations and two unknowns, the conjugate of Y_ncan be used to generate the following two equations:
X_n=A_n*H_n−B_n**G_n; and (9)
Y_n*=B_n**H_n*+A_n*G_n*. (10)

Thus, the two unknowns are A_nand B_n* and equations (9) and (10) define a matrix relationship in terms of these two unknowns as follows:

\begin{matrix} [\begin{matrix} X_{n} \\ Y_{n}^{*} \end{matrix}] = [\begin{matrix} H_{n} - G_{n} \\ G_{n}^{*} H_{n}^{*} \end{matrix}] * [\begin{matrix} A_{n} \\ B_{n}^{*} \end{matrix}] & (11) \end{matrix}

Which can be rewritten as:

\begin{matrix} [\begin{matrix} A_{n} \\ B_{n}^{*} \end{matrix}] = \frac{1}{H_{n} {\langle^{2} + ❘ G_{n} \rangle}^{2}} * [\begin{matrix} H_{n}^{*} G_{n} \\ - G_{n}^{*} H_{n} \end{matrix}] * [\begin{matrix} X_{n} \\ Y_{n}^{*} \end{matrix}] & (12) \end{matrix}

Signals A_nand B_ncan be determined using equation (12). It should be noted, that the process just described is not the only way to implement STC. Other methods can also be implemented in accordance with the systems and methods described herein. Importantly, however, by adding time diversity, such as described in the preceding equations, to the space diversity already achieved by using

base stations

1112 and1114 to communicate withdevice1116 simultaneously, the BER can be reduced even further to recover even more bandwidth.

Anexample transmitter2900 configured to communicate using STC in accordance with the systems and methods described herein is illustrated inFIG. 29.Transmitter2900 includes ablock storage device2902, a serial-to-parallel converter2904,encoder2906, andantenna2908.Block storage device2902 is included intransmitter2900 because a 1 block delay is necessary to implement the coding illustrated inFIG. 28. This is becausetransmitter2804 first transmits −b_n* (n=N−1 to 0). But b_nis the second block, so iftransmitter2900 is going to transmit −b_n* first, it must store two blocks, e.g., a_nand b_n, and then generate

block

2814aand2814b(seeFIG. 28).

Serial-to-parallel converter2904 generates parallel bit streams from the bits of blocks a_nand b_n. Encoder2906 then encodes the bit streams as required, e.g.,encoder2906 can generate −b_n* and a_n* (see

blocks

2814aand2814binFIG. 28). The encoded blocks are then combined into a single transmit signal as described above and transmitted viaantenna2908.

Transmitter

2900 preferably uses TDM to transmit messages toreceiver2806.Transmitter3000 also includesblock storage device3002, a serial-to-parallel converter3004,encoder3006, andantenna3008, which are configured to perform in the same manner as the corresponding components intransmitter2900. But in addition,transmitter3000 includesIFFTs3010 to take the IFFT of the blocks generated byencoder2906. Thus,transmitter3000 transmits −B_n* and A_n* as opposed to −b_n* and a_n*, which provides space, frequency, and time diversity.

FIG. 31 illustrates analternative system3100 that also uses FDM but that eliminates the 1 block delay associated with

transmitters

2900 and3000. Insystem3100,transmitter3102 transmits overchannel3112 toreceiver3116.Transmitter3106 transmits overchannel3114 toreceiver3116. As with

transmitters

2802 and2804,

transmitters

3102 and3106 implement an encoding scheme designed to recover bandwidth insystem3100. Insystem3100, however, the coordinated encoding occurs at the symbol level instead of the block level.

Thus, for example,transmitter3102 can transmit block3104 comprising symbols a₀, a₁, a₂, and a₃. In which case,transmitter3106 will transmit ablock3108 comprising symbols −a₁*, a₀*−a₃*, and a₂*. As can be seen, this is the same encoding scheme used by

transmitters

2802 and2804, but implemented at the symbol level instead of the block level As such, there is no need to delay one block before transmitting. An EFFT of each

block

3104 and3108 can then be taken and transmitted using FDM. AnIFFT3110 ofblock3104 is shown inFIG. 31 for purposes of illustration.

Channels

3112 and3114 can be described by H_nand G_n, respectively. Thus, inreceiver3116 the following symbols will be formed:
(A₀*H₀)−(A₁**G₀)
(A₁*H₁)+(A₀**G₁)
(A₂*H₂)−(A₃**G₂)
(A₃*H₃)+(A₂**G₃)

In time, each symbol a_n(n=0 to 3) occupies a slightly different time location. In frequency, each symbol A_n(n=0 to 3) occupies a slightly different frequency. Thus, each symbol A_nis transmitted over a slightly different channel, i.e., H_n(n=0 to 3) or G_n(n=0 to 3), which results in the combinations above.

As can be seen, the symbol combinations formed in the receiver are of the same form as equations (5) and (6) and, therefore, can be solved in the same manner, but without the one block delay.

In order to implement STC or Space Frequency Coding (SFC) diversity as described above,

bases stations

1112 and1114 must be able to coordinate encoding of the symbols that are simultaneously sent to a particular device, such as

device

1116 or1118. Fortunately,

base stations

1112 and1114 are preferably interfaced with a common network interface server. For example, in a LAN,base stations1112 and1114 (which would actually be service access points in the case of a LAN) are interfaced with a common network interface server that connects the LAN to a larger network such as a Public Switched Telephone Network (PSTN). Similarly, in a wireless WAN,

base stations

1112 and1114 are typically interfaced with a common base station control center or mobile switching center. Thus, coordination of the encoding can be enabled via the common connection with the network interface server.

Bases station

1112 and1114 can then be configured to share information through this common connection related to communications with devices at the edge of

cells

1104 and1106. The sharing of information, in turn, allows time or frequency diversity coding as described above.

It should be noted that other forms of diversity, such as polarization diversity or delay diversity, can also be combined with the spatial diversity in a communication system designed in accordance with the systems and methods described herein. The goal being to combine alternative forms of diversity with the spatial diversity in order to recover larger amounts of bandwidth. It should also be noted, that the systems and methods described can be applied regardless of he number of base stations, devices, and communication cells involved.

Briefly, delay diversity can preferably be achieved in accordance with the systems and methods described herein by cyclical shifting the transmitted blocks. For example, one transmitter can transmit a block comprising A₀, A₁, A₂, and A₃in that order, while the other transmitter transmits the symbols in the following order A₃, A₀, A₁, and A₂. Therefore, it can be seen that the second transmitter transmits a cyclically shifted version of the block transmitted by the first transmitter. Further, the shifted block can be cyclically shifted by more then one symbol of required by a particular implementation.

9. Forward Error Correction

Forward Error Correction (FEC) is used to control errors in a communication system. When FEC is included, extra bits are transmitted with the data that can be used by the receiver to check for errors in the data that was received. Depending on the implementation, the receiver can then ask that the data be resent if too many errors are detected. Alternatively, the receiver can include some mechanism by which it tries to correct detected errors.

Accordingly, as can be seen inFIG. 32, anFEC encoder3202 adds bits to aninput data stream3204 to create anoutput data stream3206 that necessarily has a higher data rate due to the added bits. In the example ofFIG. 32,FEC encoder3202 is a ½ rate FEC encoder, which means that for every input bit d_n,FEC encoder3202 adds a bit that can be used to detect errors whendata stream3206 is decoded. Thus, the data rate ofoutput3206 is twice that ofinput3204.Data stream3206 can then be modulated and transmitted to a receiver. In the receiver, anFEC decoder3208 can be used to remove the extra bits and detect errors in the original data. Thus,FEC decoder3208 should matchFEC encoder3202, i.e.,FEC decoder3208 should be a ½ rate FEC decoder, in the above example.

A problem with conventional FEC encoders and decoders is that the data rates can be too high for conventional technology. This can be especially true, for example, in an ultra-wideband application, where the data rates can be extremely high. One way to overcome this problem in accordance with the systems and methods described herein is illustrated inFIG. 33, which depicts a portion of atransmitter chain3300. In the example ofFIG. 33, adata stream3302, with a data rate (R) is first split into a plurality ofparallel data streams3306 in serial toparallel converter3304, each with a lower data rate (R/n) where n is the number of parallel data streams3306. Theparallel data streams3306 can then be encoded using a plurality of FEC encoders. Here two

encoders

3308 and3310 are illustrated. Thus, each of

FEC encoders

3308 and3310 can, depending on the implementation, handle half as much data and operate at a lower speed than required in a conventional system. More generally,

FEC encoders

3308 and3310 can be configured to assist each other with FEC encoding and reduce the overall load on each FEC encoder in the system. This, of course, requires some coordination, or message passing, between the two FEC encoders.

The outputs of

FEC encoders

3308 and3310 can then, for example, be passed through Parallel to

serial converters

3312 and3314 and combined viacombiner3316 into a single data stream with FEC encoding. The single data stream can then be optional filtered and/or pulse shaped before being modulated an transmitted, e.g., viaoptional block3318,

In another example embodiment, of an FEC encoder configured in accordance with the systems and methods described herein, a code word is generated from an input data word by adding parity bits to the data word as illustrated inFIG. 34. In this example embodiment, FEC encoder3402, referred to as a LDPC, takesdata word3404 and generatesoutput code word3406. As can be seen, the data word and code word are illustrated in matrix form. Thus, for example, the data word is a matrix comprising Arrows and 1 column.

In one embodiment of an LDPC3402, the code word can be generated using a generator matrix as illustrated by the following equation:
C_N×1=G_N×k*d_K×1 (13)
where:

- G_N×Kis the Generator Matrix
- N=M+k;
- R=k/N;
- if R=½, then M=k.

The generator matrix can, in turn, be generated from an identity matrix and a parity check matrix as illustrated in the following equation:
G=[I; P] (14)
where:

- I=the identity matrix; and
- P=the parity matrix.

Alternatively, a parity matrix H can be used to generate the code word C according to the following:
H_M×N*C_N×1=0_M×1 (15)

The parity matrix H can then be defined as:
H_M×N=[H^P_M×MH^D_M×K] (16)

Accordingly, and dropping the subscripts for simplicity:

\begin{matrix} [H^{P} H^{D}] * [\frac{\overset{⇀}{P}}{\overset{⇀}{d}}] = 0, or & (17) \\ (H^{P} * \overset{⇀}{P}) + (H^{D} * \overset{⇀}{d}) = 0 & (18) \end{matrix}

The goal now is to solve forP, sinced is known, i.e., it is the input data. To facilitate findingP in one embodiment, H^Pis configured as a dual diagonal matrix with M rows and M columns. Dual diagonal matrices are well known and will not be described here; however and exemplary one is illustrated by the following:

\begin{matrix} H^{P} = [\begin{matrix} 1 & 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & 1 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots \\ 1 \\ 0 & 0 & 0 & \dots & 0 & 1 \end{matrix}] & (19) \end{matrix}

Further, H^Dcan, depending on the embodiment, be formed from a matrix of matrices. In one embodiment, this matrix of matrices is itself block cyclic. For example, in one embodiment, 4 matrices A, B, C and D can be used as in the following:

\begin{matrix} H^{D} = [\begin{matrix} A & B & C & D \\ B & C & D & A \\ C & D & A & B \\ D & A & B & C \end{matrix}] & (20) \end{matrix}

Here, each of the matrices A, B, C, and-D will have k/4 rows and k/4 columns.

Thus, an encoder and decoder configured in accordance with the systems and methods described herein can be optimized for a dual diagonal H^Pand a block cyclic H^D, as explained below. Many methods can be used to generate matrices A, B, C, and D consistent with the systems and methods described herein. One example method, however, will be described in the following paragraphs. This example method will assume, for the time being, that k=16 and therefore k/4−=4. Then an identity matrix I can be used, such as the following:

\begin{matrix} I = [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}] & (21) \end{matrix}

Each of matrices A, B, C, and D can then be generated from this identity matrix I. For example, a permutation vector, in this example oflength 4, can then be used to generate A. Of course, other methods for generating matrices A, B, C, and D can be used consistently with the systems and methods described herein. Thus, the matrix A can, e.g., have the following form, once an appropriate permutation vector is used to modify identity matrix I:

\begin{matrix} A = [\begin{matrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix}] & (22) \end{matrix}

Basically, as can be seen, a permutation vector can be used to shift the positions of the 1's in identity matrix I. In one embodiment, a single permutation matrix can be required. Once the first matrix A is generated using the single permutation vector, then the other matrices B, C, and D can be generated by shifting matrix A. For example, in one embodiment, each subsequent matrices B, C, and D is generated by shifting he previous matrix, starting with A, by 90°. Thus, B would be as follows:

\begin{matrix} B = [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{matrix}] & (23) \end{matrix}

But as can be seen, in the example embodiment for generating matrices A, B, C, and D described above, each row has only a single 1.

In one embodiment, Galois Field algebra (GF(2)) can be used to define the following equations for use in solving forP:
1+1=0;
1−1=0;
1+0=1;
0+1=1;
0+1=1; and
0−1=−1=1. (24)

Thus, even results are equal to 0, while odd results are equal to 1.

Now returning to the equation at issue:
(H^P*P)+(H^D*d)=0 (18)

This can be rewritten as:
(H^P*P)=−(H^D*d) (25)

But using the equations (24), −1=1, therefore:
(H^P*P)=(H^D*d) (26)

In one embodiment, the following equation can be used:
(H^D*d)=u (27)

Accordingly:
(H^P8P)=u (28)

Equation (28) can be implemented effectively ifu can be generated efficiently. In on the examples above, if k=6, thenu can be determined as follows:

\begin{matrix} [\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] * [\begin{matrix} p_{5} \\ p_{4} \\ p_{3} \\ p_{2} \\ p_{1} \\ p_{0} \end{matrix}] = [\begin{matrix} u_{5} \\ u_{4} \\ u_{3} \\ u_{2} \\ u_{1} \\ u_{0} \end{matrix}] & (29) \end{matrix}

This will result in the following equations:
p₀=u₀
p₁+p₀=u₁;
p₂+p₁=u₂;
p₃+p₂=u₃;
p₄+p₃=u₄;
p₅+p₄=u₅; (30)

The equations of (30) define the following general equation:
p_n=u_n−p_n-1 (31)

This equation then suggest a configuration for anLDPC encoder3500, such as that illustrated inFIG. 35. As can be seen, theu values are fed into Exclusive-OR (XOR)3502, the output of which is fed through adelay3504 and back to the other input ofXOR3502. A remaining issue, however, is the generation of theu terms. In other words, the equation (H^P*P)=u as implemented byblock3506 should also be done in the most efficient manner possible.

In the example above, H^Dwas partitioned in 4s, therefored should also be partitioned by 4 as illustrated in the following:

\begin{matrix} \overset{⇀}{u} = [\begin{matrix} A & B & C & D \\ D & A & B & C \\ C & D & A & B \\ B & C & D & A \end{matrix}] * [\begin{matrix} {\overset{⇀}{d}}_{A} \\ \begin{matrix} {\overset{⇀}{d}}_{B} \\ \begin{matrix} {\overset{⇀}{d}}_{C} \\ {\overset{⇀}{d}}_{D} \end{matrix} \end{matrix} \end{matrix}] & (32) \end{matrix}

The above equation can be implemented efficiently, for example, using a circuit such as the example circuit illustrated inFIG. 36. The circuit ofFIG. 36 is generalized for the more realistic situation where k=128; however, it will be appreciated that the example embodiments described herein are not limited to any particular lengths or configurations. As can be seen, the circuit ofFIG. 36 uses a bank ofcyclic shift registers3606 to implement d. The outputs ofshift registers3606 can then be passed to aplurality XORs3602 as shown. Thus, XORs3202 collect the appropriate outputs fromshift registers3606 in order to generate the U terms.

But since it is known, in the examples above, that the output of each cyclic shift register will only have one 1, due to the fact that A, B, C₃and D have only one 1 in each row, the outputs ofcyclic shift registers3606 can be rearranged and fixed so that, e.g., the first outputs of each go to thefirst XOR3202, the second outputs go to thesecond XOR3202, etc. Accordingly, efficient fixedconnections3608 can be used to reduce the complexity ofLDPC3500. Theu terms can then be registered and fed toXOR3502 as illustrated.

Accordingly, if everything is segmented by 4s as illustrated in the above examples, then thecyclic shift registers3606 can be shifted k/4 times. On each clock cycle, k/4 of the solution would be generated, such that it takes k/4 cycles to get the entire solution. This can result in a highly parallel encoder, such as that illustrated inFIG. 36, for high speed operation. The result can also be a low cost encoder, because the hardware required can be reduced to ¼th that required by conventional circuits through the reuse of the components.

The LDPC encoder ofFIG. 3600 can, therefore, be used to generate code word C, which can be modulated an transmitted. But he receiver will receive C corrupted by noise as illustrated in the following:
x=(1−2C)+(noise) (33)

The job of the decoder is then to extractd from the signal represented by equation (33). In one embodiment, this can be accomplished by making soft decisions as to the value ofx and combining it with hard decisions related to the signx such thatd can then be accurately determined. The soft decisions can be based on a multilevel possibility. For example, if 4 bits are used in 2's complement, then you can have up to 16 levels. In one embodiment, the levels can, for example, be from −8 to 7. Alternatively, using offset 2's complement, the levels can be from −7.5 to 7.5. An advantage of the later is that the levels are not biased, e.g., toward the negative. An advantage of the former, however, is that it includes thelevel 0. Of course, any level scheme can be used as long as it allows for accurate determinations ofd.

The levels can be used to determine the probabilities of the value of x and ultimatelyd. For example, if the level determined forx is 7 or 7.5, then the decoder can be configured to see this as a high probability that the value is 1. If the level is −8 or −7.5, then this can be seen as a high probability that the value is −1.

Parity check equations can then be generated from the following:

\begin{matrix} [\begin{matrix} 1 & 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & 1 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots \\ 1 \\ 0 & 0 & 0 & \dots & 0 & 1 \end{matrix}] * [\begin{matrix} A & B & C & D \\ B & C & D & A \\ C & D & A & B \\ D & A & B & C \end{matrix}] * [\begin{matrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{n - 1} \end{matrix}] & (34) \end{matrix}

This will a set of parity equations in which, based on the examples above, there will be 6 terms, except in the last one, because there is exactly one 1 in each row of A, B, C, and D. The first of these parity equations would then, e.g., look like the following, based on the above examples:
S₀=x₀+x₁+x₂+x₃+x₄+x₅ (35)

Then, if S₀=+1, then the operation can be viewed as passing. If, on the other hand, it is −1, then it can be viewed as a failure. Aparity node processor3702 can be used to implement equation (35), as illustrated by the example embodiment depicted inFIG. 37. Message passing algorithms can be used to allow eachsuch node3702 to make final estimations.

FIG. 39 is a diagram illustrating and example embodiment in which a plurality ofparity node processors3702 are configured in accordance with the systems and methods described herein. Thus, eachnode3702 receives information as to what the values x₀, x₁, . . . x_Nare believed to be. A givennode3702 can then process this information and produce estimates as to what the node believes the output of the other nodes should be and feed this information back in such a manner that the subsequent input to the other nodes is modified. It should be noted, therefore, that in such an embodiment, a node does not produce information to be feedback to its own input related to what it believes its own output should be.

This is illustrated inFIG. 38 for a single node processor at time=0. As can be seen, information for each bit is provided tonode3702, which processes the information and produces information related to what it determines each bit should be. These input and outputs can be referred to as edges (E). Each output edge is feedback to the relevant input bit. Thenode processors3702 will, therefore, comprise storage to store the information being fed to it and processed as required. As a result, both storage and routing overheads can become excessive.

For example, when information related to bit xo is fed to node S₀, the information from each other node related to x₀is also added into the information provided to s₀. This is illustrated by the following:
x₀+E¹⁺¹(s₁→x₀)+E¹⁺¹(S₂→x₀)+ . . . (36)

Again, as mentioned above, in this embodiment, the edge produce by node S₀is not fed back to bit x₀.

FIG. 40 is a diagram illustrating an example decoder4000 that can be configured to reduce storage and routing overhead in accordance with one embodiment of the systems and methods described herein. The basic premise behind decoder4000 is that all the edges produced form parity node processor4002 can be added and then the last edge for each node, produced by that node, can be subtracted out. Thus, on the right hand side ofFIG. 40, a given row can be updated for all edges and then shifted inshift registers4004. The appropriate edge can then be subtracted out for each row using the data provided fromregisters4014, as opposed to doing each row, storing the result and updating it with information form other nodes.

It should be noted that the output ofshift registers4004 can be rearranged and fixed to reduce routing overhead. It should also be noted that this process provides an approximation of the correct data; however, the results converge and ultimately provide the same answer.

On the left hand side of decoder4000, eachshift register4008 gets information from only twonodes3702, e.g., via

registers

4010 and4012.

While embodiments and implementations of the invention have been shown and described, it should be apparent that many more embodiments and implementations are within the scope of the invention. Accordingly, the invention is not to be restricted, except in light of the claims and their equivalents.

Claims

1. An FEC encoder, comprising:

a plurality of block cyclic shift registers;

a plurality of fixed connections between each of the plurality of block cyclic shift registers; and

a plurality of XOR gates coupled to the plurality of fixed connections, the fixed connections fixed such that the first fixed connection between each of the plurality of block cyclic shift registers is coupled to the first of the plurality of XOR gates, the second fixed connection between each of the plurality of block cyclic shift registers is connected to the second of the plurality of XOR gates, and so on until the last of the fixed connections between each of the block cyclic shift registers is coupled to the last of the plurality of XOR gates.

2. The FEC encoder ofclaim 1, further comprising a register configured to store the output of each of the plurality of XOR gates.

3. The FEC encoder ofclaim 1, further comprising another XOR gate coupled to the output of the register, the other XOR gate configured to XOR the output of the register with a delayed version of the output of the register.

4. The FEC encoder ofclaim 1, wherein the FEC encoder is configured to produce a code word from input data bits.

5. The FEC encoder ofclaim 4, wherein the code word is generated using a parity matrix.

6. The FEC encoder ofclaim 5, wherein the parity matrix comprises a dual diagonal matrix.

7. The FEC encoder ofclaim 6, wherein the parity matrix comprises a matrix of block cyclic matrices.

8. The FEC encoder ofclaim 7, wherein the plurality of fixed connections are fixed, based on the dual diagonal matrix and the matrix of block cyclic matrices.

9. The FEC encoder ofclaim 7, wherein each of the plurality of block cyclic matrices are generated from an identity matrix and a permutation vector.

10. The FEC encoder ofclaim 9, wherein the first of the plurality of block cyclic matrices is generated directly from the identity matrix and a permutation vector, and each of the subsequent block cyclic matrices are generated by rotating the previous block cyclic matrix.

11. A wireless transmitter, comprising:

a processor configured to generate data to be transmitted by the transmitter, and

an FEC encoder configured to generate a code word based on the data, the FEC encoder comprising:

a plurality of block cyclic shift registers configured to receive the data and shift it through the plurality of block cyclic shift registers;

a plurality of fixed connections between each of the plurality of block cyclic shift registers configured to allow the data to be shifted through the plurality of block cyclic shift registers; and

12. The transmitter ofclaim 11, further comprising a register configured to store the output of each of the plurality of XOR gates.

13. The transmitter ofclaim 11, further comprising another XOR gate coupled to the output of the register, the other XOR gate configured to XOR the output of the register with a delayed version of the output of the register.

14. The transmitter ofclaim 11, wherein the code word is generated using a parity matrix.

15. The transmitter ofclaim 14, wherein the parity matrix comprises a dual diagonal matrix.

16. The transmitter ofclaim 15, wherein the parity matrix comprises a matrix of block cyclic matrices.

17. The transmitter ofclaim 16, wherein the plurality of fixed connections are fixed based on the dual diagonal matrix and the matrix of block

18. The transmitter ofclaim 16, wherein each of the plurality of block cyclic matrices are generated from an identity matrix and a permutation vector.

19. The transmitter ofclaim 18, wherein the first of the plurality of block cyclic matrices is generated directly from the identity matrix and a permutation vector, and each of the subsequent block cyclic matrices are generated by rotating the previous block cyclic matrix.