(12) United States Patent
`Stopler
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,625,219 B1
`Sep. 23, 2003
`
`US006625219B1
`
`(54) METHOD AND APPARATUS FOR
`ENCODING/FRAMING FOR MODULATED
`SIGNALS OVER IMPULSIVE CHANNELS
`
`(74) Attorney, Agent, or Firm—Darby & Darby
`(57)
`ABSTRACT
`
`(75) Inventor: Daniel Stopler, Holon (IL)
`
`(73) Assignee: Tioga Technologies, Ltd., Tel Aviv (IL)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/258,650
`(22) Filed:
`Feb. 26, 1999
`
`(51) Int. Cl.7 ............................................. .. H03M 13/00
`
`.... .. 375/240.27; 714/758
`(52)
`(58) Field of Search .......................... .. 375/260, 240.24,
`375/24027, 267; 714/755, 758; 370/468,
`479, 480
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,923,679 A * 7/1999 Itoh etal. ................. .. 714/752
`6,004,028 A * 12/1999 Bottomley
`714/758
`6,034,996 A * 3/2000 HerZberg .... ..
`375/265
`6,405,338 B1 * 6/2002 Sinha et al. .............. .. 714/752
`
`OTHER PUBLICATIONS
`
`Michael GrimWood and Paul Richardson, “S—CDMA as
`High—Capacity Upstream Physical Layer,” IEEE, 802.14A/
`98—016, Jun. 15, 1998.
`
`* cited by examiner
`Primary Examiner—Stephen Chin
`Assistant Examiner—Kevin Kim
`
`An encoding/framing scheme for multitone modulation over
`impulsive channels Which alloWs ef?cient operation in mul
`tipoint to point channels Which are affected by ingress
`(narroWband noise) and impulsive (burst) interference. The
`coding is achieved using a concatenated approach, With the
`inner code being Trellis Coded Modulation (TCM), using,
`for example, convolutional coding, and the outer code being
`a Reed Solomon (RS) code. TWo dimensional interleaving is
`performed, With one dimension being time, and the other
`dimension being frequency (tones or sub-channels). The
`TCM coding provided by the present invention is quite
`effective in dealing With impulse noise effects. The inter
`leaving may be applied in tWo levels. According to one
`embodiment, user data is RS encoded, and a portion of the
`RS encoded data is interleaved and ?lled along columns for
`transmission using a multitone transmission system. The
`remaining portion of the RS encoded user data is then TCM
`encoded, interleaved and effectively ?lled along roWs for
`subsequent transmission. In another embodiment, a portion
`of the user data is RS encoded, interleaved and ?lled along
`columns for transmission, While the remaining portion of the
`user data is instead TCM encoded, interleaved and effec
`tively ?lled along roWs for subsequent transmission. A
`diagonaliZation scheme is also used to provide immunity
`against impulse noise, While at the same time alloWing for
`a simple method of utilizing tones of different loading.
`According to the diagonaliZation principle, data packets are
`spread over time in a diagonal fashion, such that an impulse
`noise affects more than one user’s packets, With the effect on
`each being reduced. In this Way, a code having loWer
`redundancy can be used since the amount of corruption
`expected in one user’s data packet Will be reduced.
`
`42 Claims, 6 Drawing Sheets
`
`Frequency
`
`A
`
`36
`
`Impulse Noise
`
`User 1
`
`26
`
`User 2
`
`T\__
`
`-——
`
`Narrowband
`Noise
`
`Time
`
`CSCO-1012
`Cisco v. TQ Delta
`Page 1 of 17
`
`

`
`U.S. Patent
`
`Sep. 23,2003
`
`Sheet 1 of6
`
`US 6,625,219 B1
`
`2 F .QE
`
`9.
`
`E.
`
`55:69“.
`
`82%:
`
`5365025
`53:82
`
`@559“.
`
`“my-0mm
`
`Ema
`
`Page 2 of 17
`
`

`
`U.S. Patent
`
`Sep. 23, 2003
`
`Sheet 2 6f 6
`
`US 6,625,219 B1
`
`FREQUENCY
`
`l IMPULSE NOtSE
`
`l I —-—
`
`3
`i
`USER 1
`
`f)
`USER 2
`
`‘
`
`>T‘ME
`
`FIG. 2
`PRIOR ART
`
`Page 3 of 17
`
`

`
`U.S. Patent
`
`Sep. 23, 2003
`
`Sheet 3 6f 6
`
`US 6,625,219 B1
`
`FREQUENCY
`
`A
`
`l IMPULSE NOISE
`
`£__
`
`_
`
`V
`
`V
`
`USER 2
`
`/
`USER 1
`
`= TIME‘
`
`FIG. 3A
`PRIOR ART
`
`Page 4 of 17
`
`

`
`U.S. Patent
`
`Sep. 23, 2003
`
`Sheet 4 6f 6
`
`US 6,625,219 B1
`
`FREQUENCY
`
`23 ~-
`
`/"‘ USER 2
`
`I? ——
`
`USER 1
`
`FIG. 3B
`PRIOR ART
`
`Page 5 of 17
`
`

`
`U.S. Patent
`
`30023:2DeS
`
`Sheet 5 of 6
`
`US 6,625,219 B1
`
`
`
`$52mm_:aE_>o:m:_umt
`
`ucwesotwz
`
`362
`
`Page 6 of 17
`
`

`
`U.S. Patent
`
`30023:2DeS
`
`Sheet 6 of 6
`
`US 6,625,219 B1
`
`25
`
`._manms_
`
`ucm
`
`mmmfi
`
`..o_nEm._uw
`
`9.9.0
`
`._o___.._
`
`320
`
`..o>mw:mE.
`
`
`
`_m_._o=:_o>:oon.:o.0
`
`
`
`N:2mm._muo0..ouum__o0
`
`Eon;
`
`.o>a2.mE_
`
`-u$m
`
`Euoo
`
`coEo_om
`
`Page 7 of 17
`
`

`
`US 6,625,219 B1
`
`1
`METHOD AND APPARATUS FOR
`ENCODING/FRAMING FOR MODULATED
`SIGNALS OVER IMPULSIVE CHANNELS
`
`FIELD OF THE INVENTION
`
`The present invention generally relates to the ?eld of data
`communications and processing. Speci?cally, the present
`invention relates to a method and apparatus for encoding/
`framing a data stream of multitone modulated signals to
`improve impulse burst immunity.
`
`10
`
`15
`
`25
`
`35
`
`BACKGROUND OF THE INVENTION
`Digital data communications systems are commonly used
`to transmit and/or receive data betWeen remote transmitting
`and receiving locations. A central facet of any data commu
`nications system is the reliability and integrity of the data
`Which is being communicated. Ideally, the data Which is
`being transmitted from the transmitting location should be
`identical to the data Which is being received at the receiving
`location. Practically hoWever, the data to the data Which is
`being received at the receiving location. Practically
`hoWever, the data Which is received at the receiving location
`has oftentimes been corrupted With respect to the original
`data that Was transmitted from the transmitting location.
`Such data communication errors may be attributed in part to
`one or more of the transmission equipment, the transmission
`medium or the receiving equipment. With respect to the
`transmission medium, these types of data errors are usually
`attributed to the less than ideal conditions associated With
`the particular transmission medium. An example of such a
`communication medium or channel is the hybrid ?ber
`coaxial cable television netWork, HFC CATV.
`In certain channels, such as the HFC channel, errors may
`be caused by noise or other interference. One type of noise
`is ingress or narroWband interference Which typically occurs
`at a ?xed frequency and lasts for a long time. Another type
`of noise is impulse or burst interference Which typically
`occurs at unexpected times, lasts for a short period of time
`(e. g., several microseconds), and corrupts all tones or bands.
`Multitone modulation is a signal transmission scheme
`Which uses a number of narroW-band carriers positioned at
`different frequencies, all transmitting simultaneously in par
`allel. Each narroW band carries a fraction of the total
`information being transmitted. The discrete bands or sub
`channels are independently modulated, and each have a
`carrier frequency at the center frequency of the particular
`band.
`One type of multitone transmission scheme is discrete
`multitone, often referred to as DMT. In DMT, a 1.1 MHZ
`channel is broken doWn into 256 sub-channels or bands,
`each of Which is 4 KHZ. Each of the sub-channels has its
`oWn carrier frequency, and the signal to noise ratio for each
`of the sub-channels is monitored by the DMT system to
`determine hoW many bits per signal may be carried in each
`of the sub-channels. Each of the sub-channels transmits a
`number of information bits in a single symbol or signal
`period. The number of bits per signal (or symbol) in a
`sub-channel is typically referred to as the “loading” of the
`sub-channel. The DMT system dynamically adjusts the
`loading of each of the sub-channels in accordance With the
`noise characteristics of the sub-channel. Particularly noisy
`sub-channels may sometimes not be used altogether.
`DMT typically has long symbol periods of 250 micro
`seconds. As a result, DMT exhibits fairly good immunity
`With respect to time domain events, since the effect of a time
`
`45
`
`55
`
`65
`
`2
`domain event Will be averaged out over the relatively long
`symbol period. In this Way, impulse noise has less of an
`effect on DMT transmissions. Although the effect is reduced,
`there is nevertheless, still an adverse effect due to impulse
`noise. With respect to narroWband interference, this type of
`noise is typically stable and can be compensated for by
`adjusting the loading of the particular, affected sub
`channels.
`Variable Constellation Multitone (VCMT) modulation is
`a transmission scheme speci?cally designed to effectively
`combat the high ingress and burst impairments in cable TV
`channels, and also to maximiZe the throughput capacity of
`such channels. VCMT uses variable bit loading per tone,
`along With coding and interleaving. The tones are indepen
`dently modulated from QPSK (quadrature phase shift
`keying) to 256-QAM (quadrature amplitude modulation),
`depending on the noise measured for each tone. The SNR
`(signal to noise ratio) across the channel is monitored for
`each tone, and the headend receiver accordingly instructs the
`upstream transmitter in the cable modem to modify the
`QAM constellation for each tone to maintain a desired BER
`(bit error rate).
`VCMT also utiliZes spectral shaping to reduce the fre
`quency sidelobes of the tones, as compared With conven
`tional multitone modulation, in order to reduce the effect of
`narroWband interference to only those affected tones. As
`With all multitone modulation schemes, VCMT utiliZes long
`symbol periods to average the effect of burst and impulse
`noise. Interleaving the data over time and frequency may
`also be used to minimiZe the number of impaired tones for
`each user.
`The VCMT nominal con?guration is designed for a
`bandWidth of 1.6 MHZ. HoWever, the VCMT con?guration
`may be adapted for any particular bandWidth through proper
`modi?cation of the system parameters. In the case of the
`nominal con?guration, VCMT uses the folloWing param
`eters:
`
`RF Bandwidth:
`Number of tones:
`Modulation:
`Inter-tone spacing:
`Signaling rate:
`Data rate:
`
`Symbol shaping:
`
`0.09
`Symbol duration:
`
`1.6 MHZ.
`36
`QPSK to 256-QAM (per tone)
`43.75 KHZ.
`40 kbaud (per tone)
`Variable, depending on tone
`modulation
`Modi?ed square-root-raised
`cosine, roll-off
`
`10 symbol periods
`(250 microseconds)
`
`Code Division Multiple Access (CDMA) modulation is a
`multi-user access transmission scheme in Which different
`users overlap both in frequency and in time. This is in
`contrast to Frequency Division Multiple Access (FDMA) in
`Which users overlap in time, but are assigned unique
`frequencies, and Time Division Multiple Access (TDMA) in
`Which users overlap in frequency, but are assigned unique
`timeslots. According to CDMA, each user is assigned a
`unique code sequence that alloWs the user to spread its
`information over the entire channel bandWidth, as opposed
`to particular sub-channel(s) in FDMA. Thus, signals from all
`users are transmitted over the entire channel. To separate out
`the signals for a particular user at a receiver, cross correla
`tion is performed on the received signal using the unique
`user code sequence. In CDMA systems, inter-user interfer
`ence is minimiZed using one of tWo possible techniques.
`
`Page 8 of 17
`
`

`
`US 6,625,219 B1
`
`3
`The ?rst technique for minimizing inter-user interference
`is to modulate the user signals using an orthogonal basis of
`Wideband functions, e.g., Walsh basis. Speci?cally, at a
`given instant in time, each user selects (according to its
`unique code) a different basis function from the orthogonal
`basis, ensuring Zero cross correlation betWeen the different
`users. The, basis function used by each user may be changed
`on a symbol by symbol basis, While still ensuring that
`different users use different functions. The orthogonal basis
`itself may be changed on a symbol by symbol basis. The
`result is that each user occupies the entire channel
`bandWidth, While user cross correlation is kept to Zero. The
`disadvantage of this approach is that in order to build a
`Wideband (and frequency overlapping) orthogonal basis, the
`user data generally needs to be time synchroniZed since the
`orthogonal base construction assumes time synchroniZation.
`Asecond technique for minimiZing inter-user interference
`Which does not require that the user data be time synchro
`niZed is to modulate each symbol using a pseudo randomly
`selected Wideband Waveform, Which is selected according to
`the unique code for each user. The Wideband Waveform may
`be generated by multiplying the user data by a pseudo
`random sequence, referred to as a spreading sequence. This
`approach minimiZes inter-user interference, but does not
`reduce the interference to Zero. HoWever, the loWer the
`signaling rate (baud rate) is versus its bandWidth, the loWer
`the cross correlation Will be. Thus, in CDMA the signaling
`rate of each user is usually much smaller than the channel
`bandWidth it occupies in order to make the inter-user inter
`ference manageable. Typically, a ratio of 1/100 or less is
`common.
`The above tWo methods for minimiZing inter-user inter
`ference may be combined, for example, When it is possible
`to group users, such that time synchroniZation exists Within
`a group, although time synchroniZation may not exist across
`groups.
`CDMA transmission is Well knoWn to those of skill in the
`art. A comparison betWeen CDMA and FDMA/TDMA may
`be found in Proakis, “Digital Communications”, Chapter 15,
`Which is incorporated herein by reference. Also, an example
`of the combination of the above tWo approaches for mini
`miZing inter-user interference (i.e., combining a Walsh basis
`Within a group and a spreading sequence across groups) may
`be found in TIA/EIA/IS-95 “Mobile Station Compatibility
`Standard for Dual Mode Wideband Spread Spectrum Cel
`lular System”, Which is incorporated herein by reference.
`The multitone transmission schemes described above,
`DMT, VCMT and CDMA, may be conceptually vieWed as
`a tWo-dimensional matrix, With time as the horiZontal axis
`and frequency as the vertical axis. In the presence of ingress
`(narroWband interference), in the case of CDMA, all codes
`are corrupted by the ingress, While in VCMT, a single roW
`(or tone) is corrupted, and in DMT, the ingress affects
`primarily a single roW (or tone) With a much lesser effect on
`adjacent roWs. In the presence of impulse (burst
`interference), the effect on CDMA and DMT is the corrup
`tion of a single symbol, While the effect on VCMT is the
`corruption of primarily a single symbol.
`To overcome these problems, data communications sys
`tems often rely on error detection and error correction
`schemes, to detect the occurrence of a data error and to
`correct a data error, respectively. One simple form of error
`detection is the use of a parity bit associated With each block
`of data to indicate Whether the particular block contains an
`odd or even number of 1 bits. HoWever, this is a very simple
`scheme Which has numerous disadvantages. It is a simple
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`4
`type of error detection scheme Which is capable of accu
`rately detecting up to one bit error per data block. Moreover,
`the use of a parity bit cannot detect the occurrence of tWo bit
`errors in a data block, since this is not even detected as a
`parity violation. Additionally, the use of a parity bit only
`detects errors; it cannot correct errors. Any time that an error
`is detected, the receiving location typically requests retrans
`mission of the particular data block from the transmitting
`location.
`One type of error correction scheme commonly used in
`data communications systems is the use of redundant data
`transmissions and a voting circuit at the receiving location.
`In such a system, the data being transmitted is repeated a
`number of times, such as ?ve. At the receiving location, all
`?ve data blocks are received and processed by a voting
`circuit Which compares the ?ve received versions of each
`data bit and determines the bit to be a 1 or 0 based on the
`voting consensus. Although such a system is capable of
`detecting and correcting data errors, it does so at a great cost
`in terms of the effective data throughput or transmission rate.
`This is due to the fact that each data block must be repeated
`a number of times.
`The above-mentioned correction/detection schemes are
`examples of binary block codes. Speci?cally, an (n,k,d)
`binary block code is a set of 2k binary codeWords of block
`length n and minimum distance d (i.e., coding distance). The
`transmitted data is partitioned into binary blocks of length k,
`then each block is mapped into a binary codeWord of length
`n, Which is then modulated and transmitted through the
`channel, or sub-channels in the case of multiple sub
`channels, such as in DMT or VCMT. This block code is
`capable of correcting up to t=(d—1)/2 errors Within each
`codeWord.
`As mentioned above, there are cases Where channel errors
`occur in non-frequent bursts, the length of Which exceeds the
`error correction capability of the code. These cases are
`handled by interleaving the data stream before it is modu
`lated and transmitted through the channel. Functionally, an
`interleaver is a memory device Which is used to rearrange
`and separate the codeWords or frames Which are to be
`transmitted. Although certain aspects of the present inven
`tion are described by Way of reference to interleavers, such
`as block interleavers, it should be understood that any type
`of interleaving, such as for example, convolutional
`interleaving, may be used. The terms codeWord and frame
`are used interchangeably herein Where a frame includes only
`one codeWord. Instead of transmitting a succession of com
`plete codeWords, the interleaver alloWs the transmission of
`a portion (such as a byte) of a ?rst codeWord, folloWed by
`a portion of a second codeWord, and so on. Henceforth, these
`portions Will be referred to as either symbols or codeWord
`symbols. In this Way, if an error burst occurs during
`transmission, the error burst Will not be localiZed to one
`particular frame. Rather, the errors Will be spread across
`several codeWords. If the errors Were completely Within one
`codeWord, they may exceed the number of errors Which the
`system can inherently correct for by the use of a block code.
`By spreading the data errors across several blocks, the
`number of errors Within each block may be reduced to the
`point Where the system is capable of correcting the data
`errors.
`In a simple interleaver, data is Written into the memory in
`columns and then read out in roWs for subsequent transmis
`sion. At the receiver end, the received data is Written into a
`de-interleaver in roWs and then read out in columns. The
`interleaver rearranges the data Within the codeWords, and the
`de-interleaver essentially performs the reverse process to
`
`Page 9 of 17
`
`

`
`US 6,625,219 B1
`
`5
`reconstruct the codewords for subsequent use. In this type of
`interleaver, all the data Write operations are carried out as a
`group, and then the data read operations are carried out as a
`group. This type of interleaving, referred to as block
`interleaving, introduces latency of one block at the trans
`mitter and one block at the receiver, due to the fact that a
`complete block has to be Written before it can be read.
`
`SUMMARY OF THE INVENTION
`The present invention is for an encoding/framing scheme
`for multitone modulation over impulsive channels. The
`encoding/framing scheme alloWs ef?cient operation in mul
`tipoint to point channels Which are affected by ingress
`(narroWband noise) and impulsive (burst) interference. The
`coding is achieved using a concatenated approach, With the
`inner code being Trellis Coded Modulation (TCM), using,
`for example, convolutional coding, and the outer code being
`a Reed Solomon (RS) code. TWo dimensional interleaving is
`performed, With one dimension being time, and the other
`dimension being frequency (tones or sub-channels). In con
`trast to conventional coding schemes, the TCM coding
`provided by the present invention is quite effective in
`dealing With impulse noise effects. The present invention is
`also for a tWo level interleaving approach, in Which different
`interleaving is performed on different levels. According to
`one embodiment of the present invention, the user data is RS
`encoded, and a portion of the RS encoded data is interleaved
`and ?lled along columns for transmission using a multitone
`transmission system. The remaining portion of the RS
`encoded user data is then TCM encoded, interleaved and
`effectively ?lled along roWs for subsequent transmission. In
`another embodiment according to the present invention, a
`portion of the user data is RS encoded, interleaved and ?lled
`along columns for transmission, While the remaining portion
`of the user data is instead TCM encoded, interleaved and
`effectively ?lled along roWs for subsequent transmission.
`The actual ?lling of the TCM encoded data may be per
`formed along columns; hoWever, the interleaving essentially
`introduces a reversal betWeen columns and roWs, such that
`the effective ?lling of data is along roWs. In addition to the
`reversal of columns and roWs, the interleaving also intro
`duces time separation of symbols, Which is a function of the
`interleaver depth.
`The advantage of this approach is that the RS code
`symbols are ?lled in columns, While the TCM codeWords are
`?lled in roWs. The ?rst effect is that the number of RS bytes
`that are impacted by an impulse is reduced. OtherWise, an
`impulse could affect a larger number of RS bytes if they
`Were ?lled in roWs. Although the impacted RS bytes might
`be more severely impacted, due to the nature of the RS
`coding, it does not matter Whether the RS byte is corrupted
`by one bit or by many bits. Thus, the advantage of the
`present invention is reducing the total number of RS bytes
`Which contain any corrupted bits. The second effect is that
`the TCM codeWords are ?lled in along roWs, Which in the
`case of an impulse, reduces the number of bits corrupted in
`each corrupted codeWord. Again, because of the nature of
`the TCM coding, it is preferable to reduce the maximum
`number of corrupted bits likely to be experienced, in order
`to reduce the coding redundancy required of all codeWords.
`The present invention is also for a diagonaliZation scheme
`Which provides immunity against impulse noise, While at the
`same time alloWing for a simple method of utiliZing tones of
`different loading. According to the diagonaliZation principle,
`data packets are spread over time in a diagonal fashion, such
`that an impulse noise affects more than one user’s packets,
`With the effect on each being reduced. In this Way, a code
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`having loWer redundancy can be used since the amount of
`corruption expected in one user’s data packet Will be
`reduced.
`The present invention Will become more apparent from
`the folloWing Brief Description of the DraWings and
`Description of Preferred Embodiments.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a multitone modulation data
`transmission system;
`FIG. 2 is an illustration of multitone data transmission as
`a function of time;
`FIG. 3A is an illustration of multitone data transmission
`as a function of time, With roWs and columns interchanged,
`for the case of uniform tone loading;
`FIG. 3B is an illustration of multitone data transmission
`as a function of time, With roWs and columns interchanged,
`for the case of nonuniform tone loading;
`FIG. 4 is an illustration of diagonaliZation in accordance
`With the present invention for multitone data transmission as
`a function of time;
`FIG. 5 is a block diagram of the framing approach of the
`present invention.
`
`DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`FIG. 1 shoWs a block diagram of a multitone modulation
`system. Such a system may be used in a multipoint to point
`channel, in Which the communication channel is shared
`betWeen users (stations), using, for example, Time Division
`Multiple Access (TDMA). A TDMA system allocates dis
`crete amounts of the frequency bandWidth to each user,
`alloWing many simultaneous conversations or connections.
`In a TDMA system, each user is assigned a speci?c timeslot
`for transmission of the data packets associated With that user.
`The “packet” is the user transmission unit of data. Referring
`noW to FIG. 1, a data packet 12 is processed by a framing
`block 14 Which performs the coding and interleaving func
`tions used to improve immunity against interference. The
`packets processed by the framing block 14 are passed to the
`multitone modulation block 16 Which performs the multi
`tone modulation, as described in detail beloW, and generates
`a baseband multitone signal. The baseband multitone signal
`is then passed to frequency upconversion block 18 Which
`converts the baseband signal to its assigned frequency band.
`The present invention concatenates TCM inner coding
`and RS outer coding. Speci?cally, in the TCM coding, signal
`space is partitioned into cosets encoded by a rate 1/2 convo
`lutional encoder. TCM coding is very ef?cient in White noise
`channels. As a result, it ef?ciently utiliZes the spreading
`effect of impulse energy betWeen tones, assuming proper
`interleaving. Although the input noise may not be pure White
`noise, but may in fact be colored, the adaptive, per-tone bit
`loading effectively provides White noise conditions for the
`coset encoding.
`The RS outer coding provides additional protection
`against noise. It is mostly effective against strong impulses
`Which have penetrated to the TCM parallel transitions layer.
`Due to the high performance of the TCM coding and the
`long symbols used in VCMT, it is possible to use RS coding
`With loWer redundancy.
`In accordance With the tWo dimensional interleaving
`according to the present invention, coded data is time
`interleaved and assigned to tones in a Way Which evenly
`divides the effect of ingress and impulse noise over multiple
`
`Page 10 of 17
`
`

`
`US 6,625,219 B1
`
`7
`codewords and among multiple users. First, inter-user inter
`leaving is performed using a diagonal structure to assign
`tones among different users. The diagonaliZation scheme
`complements the inherent multitone immunity to impulse
`noise. As a result, impulse energy is divided betWeen tones,
`and tones are assigned to different users. Intra-user inter
`leaving is used to interleave codeWords Within a packet in a
`Way Which divides the interference effect betWeen
`codeWords, While keeping the RS symbols aligned (column
`Wise) With the impulse interference. This alignment
`approach makes use of the RS code’s ef?cient burst handling
`capabilities.
`FIG. 2 illustrates a multitone modulation scheme utiliZing
`TDMA. A number of tones T are positioned at different
`frequency bands along the vertical frequency axis. Data
`packets are transmitted in a time-Wise fashion along the
`horiZontal time frequency axis. In the speci?c example
`shoWn in FIG. 2, User 1 is allocated tWo timeslots, While
`User 2 is allocated ?ve timeslots folloWing the transmission
`of User 1. The presence of impulse noise Will act to corrupt
`a column of data. Because impulse noise has the potential to
`corrupt a very high percentage of data for a particular user,
`the data for all users must be encoded using a high degree
`of redundancy in the event that it is corrupted. This approach
`is extremely inefficient in that user data for all users must be
`encoded to have a very high degree of compensation When
`only a small number of users are likely to have their data
`corrupted.
`One approach to reducing the effect of impulse noise is
`shoWn in FIG. 3A, in Which the columns and roWs are
`essentially sWitched. Reducing the effect of impulse noise
`Will result in a reduction in the amount of encoding or
`compensation that is required to effectively deal With
`expected noise events. As shoWn in FIG. 3A, each timeslot
`along the horiZontal time axis is split among users. The tones
`T in FIG. 3A are assumed to all have the same bit loading.
`The speci?c example shoWn in FIG. 3A illustrates tWo
`“timeslots” for tWo users, User 1 and User 2. As a result, the
`effect of any impulse noise Will be split among different
`users, and Will not be concentrated on the data of a single
`user. Essentially, the corrupted data is distributed more
`evenly among users, thus reducing the maximum percentage
`of corrupted data Which is likely to be experienced. As a
`result, the required coding redundancy or compensation
`necessary to deal With expected errors may be reduced. This
`is in contrast to the approach illustrated in FIG. 2, in Which
`case the impulse noise may be completely targeted on the
`data of a single user, resulting in a large number of errors,
`thus requiring a high degree of redundancy or compensation
`in the coding of all user data.
`Although the approach of FIG. 3A may increase noise
`immunity, it still has its disadvantages. Speci?cally, the
`sWitching of columns and roWs is only practical for multi
`tone transmission systems in Which the individual tones all
`have the same loading. In the simplistic example of FIG. 2,
`User 1 is transmitting an amount of data corresponding to
`seven sub-channels for tWo time intervals. Similarly, User 2
`is transmitting an amount of data corresponding to the same
`seven sub-channels, but for ?ve time intervals. When the
`roWs and columns are reversed, as in FIG. 3A, the amount
`of data for User 1 noW corresponds to the ?rst tWo sub
`channels, but for a longer period of time. Similarly, the
`amount of data for User 2 corresponds to the next ?ve
`sub-channels, for the same period of time. This limitation,
`i.e., uniform loading, is required so that the system can be
`easily and practically implemented With uniform siZed
`rectangles, so that in this example, the data transmitted by
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`8
`seven sub-channels for tWo time periods, Would be the same
`amount of data as that transmitted by tWo sub-channels for
`seven time periods. Of course, the system may be imple
`mented With nonuniform tone loading; hoWever, the system
`must then have to contend With irregularly shaped rect
`angles.
`The application of the principles of FIG. 3A (i.e., sWitch
`ing of columns and roWs) in the case of nonuniform bit
`loading is illustrated in FIG. 3B. For this illustration of
`nonuniform bit loading, it is assumed that tones 11 and 13
`have bit loading of 2, While tones 15, 17, 19, 21 and 23 have
`bit loading of 1. Thus, in the original case of FIG. 2, User
`1 data Will correspond to tones 11 and 13 (tWo bits each) for
`tWo time periods, or eight bits, plus tones 15, 17, 19, 21 and
`23 (one bit each) for tWo time periods, or 10 bits, for a total
`of 18 bits. Similarly, the data for User 2 Will correspond to
`tones 11 and 13 (tWo bits each) for ?ve time periods, or 20
`bits, plus tones 15, 17, 19, 21 and 23 (one bit each) for ?ve
`time periods, or 25 bits, for a total of 45 bits. Thus, if the
`roWs and columns are reversed, as shoWn in FIG. 3B, User
`1 is noW assigned tones 11 and 13 (tWo bit loading for each),
`Which require ?ve time periods to transmit the 18 bits for
`User 1. Similarly, User 2 is assigned tones 15, 17, 19, 21 and
`23 (one bit loading for each), Which require nine time
`periods to transmit the 45 bits for User 2. As a result, the
`system must contend With irregular shaped rectangles, as
`shoWn in FIG. 3B.
`The present invention solves the above problem by uti
`liZing the diagonaliZation principle illustrated in FIG. 4. As
`shoWn in FIG. 4, a frequency (sub-channel) versus time
`mapping is used to transmit the data packets for the different
`users. The speci?c mapping shoWn in FIG. 4 is a linear
`frequency versus time mapping having a slope of 1, i.e., the
`tone index is incremented by one for each successive symbol
`time period. Other slopes may be used in accordance With
`the principles of the present invention. In the illustrated
`example, the data packet for User 1 consists of tWo diago
`nals 22, 24, While the data packet for User 2 consists of ?ve
`diagonals, 26, 28, 30, 32 and 34. Because the data for the
`different users is spread out in time, the effect of impulse
`noise is also similarly spread out. For example, the impact
`of impulse noise 36 Will be spread out over both User 1 and
`User 2. The advantage of this approach is that the amount of
`corrupted data that any one user is expected to experience is
`decreased. As a result, the level of redundancy or compen
`sation required in the coding for such data is also reduced,
`thereby reducing the inef?ciency and overhead associated
`With proper data transmission. More importantly, the present
`invention provides added immunity against im