Method and apparatus for processing bit-interleaved data traffic in a communication network

Abstract

A manner of processing bit-interleaved data traffic in a communication network. In the increasingly-common scenario where data traffic is bit interleaved and scrambled using a PRBS (pseudo-random binary sequence) before it is transmitted from a sender to a receiver, the receiver is configured to receive the transmitted bit stream and decimate it, that is, remove the bits of the bit stream that are allocated for the receiver, prior to descrambling. To accomplish this, the receiver employs an LFSR (linear feedback shift register) similar or identical to the one used by the sender to scramble the data. The LFSR is initialized by employing helper bits inserted by the sender or an initialization unit, and may employ other techniques for phase adjustment or state skipping depending on the nature of the transmitted bit stream.

Claims

1. A communication system comprising a first receiver, the first receiver comprising: a network interface for receiving a scrambled bit stream interleaved to include bits allocated for the first receiver and bits allocated for at least a second receiver; a extractor downstream of the network interface configured to extract from the interleaved bit stream only bits allocated for the first receiver; and a descrambler downstream of the extractor for descrambling the allocated bits extracted from the interleaved bit stream.

2. The communication system of claim 1, further comprising a transmitter, the transmitter comprising a bit stream scrambler.

3. The communication system of claim 2, wherein the bit stream scrambler comprises an m-bit LFSR (linear feedback shift register).

4. The communication system of claim 1, wherein the first receiver is an ONU.

5. The communication system of claim 1, wherein the first receiver is a wireless device.

6. The communication system of claim 1, wherein the descrambler comprises an m-bit LFSR having a feedback loop comprising at least one XOR gate adder having as a first input the output of the m.sup.th register of the LFSR and having as a second input an LFSR tap positioned between the first register of the LFSR and the m.sup.th register of the LFSR.

7. The communication system of claim 6, wherein the at least one XOR gate adder comprises a plurality of XOR gate adders in series, each XOR gate adder having as a second input an LFSR tap positioned between the first register of the LFSR and the m.sup.th register of the LFSR.

8. The communication system of claim 6, wherein the received interleaved bit stream has been scrambled using a PRBS (pseudo-random binary sequence) characterized by an MLS (maximum length sequence).

9. The communication system of claim 8, wherein the LFSR comprises an input selector having as a first input the output of the feedback loop and as a second input the extracted bit stream from the decimator, wherein input selector selects the input to the first register of the LFSR.

10. The communication system of claim 9, wherein the input selector is configured to select the second input for the first m bits of the extracted bit stream corresponding to a data frame and to select the first input otherwise.

11. The communication system of claim 10, wherein the descrambler further comprises an output XOR gate adder having as a first input the output of the feedback loop and as a second input the allocated bit stream from the decimator, wherein the output of the output XOR gate adder is the descrambled data.

12. The communication system of claim 11, wherein the descrambler further comprises: an output selector having as a first input the output of the m.sup.th register of the LFSR and having as a second input the output of the feedback loop; and as a second input the allocated bit stream from the decimator, wherein the output of the output of the output selector is provided to the output XOR gate adder.

13. The communication system of claim 1, further comprising an initialization unit.

14. The communication system of claim 13, further comprising a plurality of input selectors, each input selector having as a first input the output of a preceding register of the LFSR and having as a second input an output of the initialization unit.

15. The communication system of claim 1, further comprising a phase shift computation unit.

16. A method of processing bit-interleaved traffic in a communication system, comprising: receiving at a first receiver a scrambled bit stream interleaved to include bits allocated for the first receiver and bits allocated for at least a second receiver; extracting by the first receiver from the interleaved bit stream only bits allocated for the first receiver; and descrambling the allocated bits extracted from the interleaved bit stream.

17. The method of claim 16, wherein the received interleaved bit stream has been scrambled using a PRBS characterized by an MLS. wherein the received interleaved bit stream has been scrambled using a PRBS (pseudo-random binary sequence) characterized by an MLS (maximum length sequence).

18. The method of claim 17, wherein the descrambler comprises an m-bit LFSR and further comprising initializing the LFSR.

19. The method of claim 18, wherein the bit stream comprises helper bits and initializing the LFSR comprises loading the bits of the received allocation corresponding to the helper bits into the LFSR registers.

20. The method of claim 18, wherein initializing the LFSR comprises loading bits from an initialization unit.

21. The method of claim 16, further comprising discarding by the receiver received bit-stream bits not allocated for the first receiver.

22. The method of claim 16, further comprising interleaving, by a transmitter, a plurality of receiver bit streams to form the interleaved bit stream, scrambling the interleaved bit stream, and transmitting the scrambled interleaved bit stream.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) A more complete understanding of the present invention may be obtained by reference to the following detailed description when taken in conjunction with the accompanying drawings wherein:

(2) FIG. 1 is a simplified schematic diagram illustrating a P2MP network;

(3) FIG. 2 is an exemplary frame structure illustrating a typical bit-interleaved format;

(4) FIG. 3 is a simplified block diagram illustrating selected components of a receiver of the prior art;

(5) FIG. 4 is a simplified block diagram illustrating selected components of a receiver that is operational according to an embodiment of the present invention;

(6) FIG. 5 is a schematic diagram illustrating a descrambler according to an embodiment of the present invention;

(7) FIG. 6 is a flow diagram illustrating a method according to this embodiment of the present invention;

(8) FIG. 7 is a schematic diagram illustrating a descrambler according to another embodiment of the present invention;

(9) FIG. 8 is a phase shift graph illustrating the phase shift corresponding to certain receiver IDs depending on an LFSR initial state and characterizing polynomial as explained in Example 1;

(10) FIG. 9 is a phase shift graph illustrating the phase shift corresponding to certain receiver IDs depending on an LFSR initial state and characterizing polynomial as explained in Example 1;

(11) FIG. 10 is a phase shift graph illustrating the phase shift corresponding to certain receiver IDs depending on an LFSR initial state and characterizing polynomial as explained in Example 2;

(12) FIG. 11 is a phase shift graph illustrating the phase shift corresponding to certain receiver IDs depending on an LFSR initial state and characterizing polynomial as explained in Example 2;

(13) FIG. 12 is a schematic diagram illustrating a general implementation of a skipping descrambler according to an embodiment the present invention.

(14) FIG. 13 is a schematic diagram illustrating a descrambler according to another embodiment of the present invention;

(15) FIG. 14 is a flow diagram illustrating a method according to another embodiment of the present invention;

(16) FIG. 15 is a schematic diagram illustrating a descrambler according to another embodiment of the present invention;

(17) FIG. 16 is a schematic diagram illustrating a descrambler according to another embodiment of the present invention; and

(18) FIG. 17 is a schematic diagram illustrating an initialization unit according to another embodiment of the present invention.

DETAILED DESCRIPTION

(19) The present invention is directed to a manner of processing bit-interleaved data traffic in a communication network. Specifically, the present invention may be used to advantage where bit-interleaved traffic is scrambled using a PRBS (pseudo-random binary sequence). As mentioned above, bit-interleaved and scrambled data traffic may be advantageously employed in PtMP (point to multi-point) environments, where a single sending unit transmits to multiple receivers that each extract that portion of the data frames that are intended for them. Note, however, that the present invention may be useful and implemented in other environments as well, for example those employing PtP (point to point) communications (which may be viewed as a special case of PtMP).

(20) Although bit interleaving brings some efficiency to a communication environment, it introduces some inefficiencies as well. In the conventional approach, illustrated in FIG. 3, the interleaved and scrambled bit stream 35 is received at the network interface 41 of receiver 40. The received bit stream is then passed to a descrambler 45 where it is descrambled, and the descrambled bit stream 46 is then passed to a decimator 50. Decimator 50 produces a bit stream 55 that includes the bits of the received bit stream 35 that were allocated for receiver 40. The descrambled and de-interleaved bit stream 55 is then passed along for further processing.

(21) As noted in FIG. 3, and as is true in most cases, incoming bit stream 35 is received at the rate of transmission, R.sub.t, which not unexpectedly is much faster than the rate R.sub.i of bit stream 55. This means that the descrambler 45 and the decimator 50 must both operate at the higher rate. In addition, the descrambler 45 must process the entire bit stream 35. The remaining elements (not shown) of receiver 40, of course, efficiently process the smaller allocated bit stream 55 at the much slower rate R.sub.i.

(22) The inventors have discovered that this efficiency may be extended by proper configuration and operation of the receiver, especially in a PtMP environment where bit interleaving provides advantages. Several embodiments of this configuration will now be described in further detail.

(23) FIG.4 is a simplified block diagram illustrating selected components of a receiver 100 operational according to an embodiment of the present invention. In this embodiment, receiver 100 includes a network interface 105 that receives bit interleaved and scrambled bit stream 101. Note that the network interface will vary depending on the transmission medium, and may be essentially the same or similar to the network interface 41 depicted in FIG. 3.

(24) In the embodiment of FIG. 4, the received bit stream 101 is provided by the network interface to decimator 110. Decimator 110 produces a bit stream 111 that carries the bits of the received bit stream 101 that were allocated for receiver 40. Bits not intended for receiver 40 are discarded or ignored. Here it is noted that the operation of decimator 110 may be but is not necessarily the same as the operation of decimator 50 shown in FIG. 3. Allocated bit stream 111 from decimator 110 is then provided to descrambler 115, which is configured according to the present invention.

(25) In this embodiment, descrambler 115 then descrambles only the allocated bit stream 111 provided to it, a process further described below. Notably, while the transmitted bit stream 101 arrives at the receiver 100 at the rate R.sub.t, the descrambling process is performed at the much lower rate R.sub.i. This is possible because the descrambler 115 only has to descramble the allocated bit stream 111, which is received from decimator 110 at the lower rate. An increase in the efficiency is expected in all or almost all implementations. Note, however, that no particular rate differential or efficiency increase is a requirement of the present invention unless explicitly recited in a particular embodiment. The decimated and descrambled bit stream 120 is then passed along to downstream elements (not shown) of receiver 100 for further processing.

(26) Note that in most implementations, there are multiple receivers of the bit stream 35, in many cases each processing the bit-interleaved and scrambled bit stream in the same fashion. While this is not a requirement, it is preferred, and for convenience the invention will be described herein based on a network in which all receivers are operating according to the same principle.

(27) Some notation may be assigned for use herein. In its general form, a bit-interleaved frame (for example frame 20 shown in FIG. 2) transmitted by the sender carries the traffic for a particular receiver i, where i=1, 2, . . . , N, at every K.sub.i th bit starting at a particular bit position S.sub.i in the frame and ending at a later bit position T.sub.i. The triplet (S.sub.i, T.sub.i, K.sub.i) then identifies the location of receiver i's bits as the allocation for receiver i.

(28) Note that the allocation may be static or dynamic. Dynamic allocations can vary every frame or after several frames, and not necessarily in a periodic manner As mentioned above, the header field allocation is typically static and regular, and frequently any dynamic allocation is communicated to the relevant receiver or receivers in the header field of the transmission frame, although other mechanisms may be used. Some manner of ascertaining the allocation is of course necessary for the decimator to properly remove the allocated bits.

(29) In implementing the present invention, it is of course desirable that the decimation and descrambling be done properly. The decimated bit stream must accurately include those bits intended for the receiver performing the decimation. As mentioned above this can be assured by allotment information that is either agreed upon in advance or extracted from the transmitted frames themselves, normally from the header portion.

(30) Descrambling after the decimation may be successfully performed by processing the bit stream in a number of different ways, several of which will now be described as separate embodiments. The desirability of each of these embodiments may vary according to factors such as whether the data frame payload allotment is static or dynamic and the selection of the allocation interval K.sub.i.

(31) Note that all mathematical operations described herein are over the binary field unless stated otherwise or clear from the context.

(32) First Embodiment

(33) In a first embodiment, a modified (interleaved, scrambled) bit stream is transmitted by the sending device and received by the receiver, for example at interface 105 of receiver 100 shown in FIG. 4. A configuration and operation of the receiver descrambler for this embodiment will now be described.

(34) FIG. 5 is a schematic diagram illustrating a descrambler 200 according to an embodiment of the present invention. In this embodiment, the descrambler 200 receives the allocated bit stream and outputs the descrambled data, as noted in FIG. 5 (refer also to FIG. 4). Descrambler 200 includes an LFSR 210 having m registers (referred to here as 1, 2 . . . m−1, m). As indicated by the ellipsis, there may be any number of such registers in a given descrambler; as an example, a GPON system may use 8 though for XGPON designs the number may go as high as 58. The number of registers will usually correspond to the number of registers in the scrambling LFSR, though as should be apparent a receiver could be constructed with extra components that could be switched into or out of service to adjust for different values of m.

(35) In the embodiment of FIG. 5, XOR gates 215.sub.1, 215.sub.2, . . . 215.sub.m−1 are serially provided in the feedback loop 215. As can be seen, in this embodiment there is a tap (or potential tap) following each register in LFSR 210, and a switch 220.sub.1, 220.sub.2, . . . 220.sub.m−1, for activating the associated tap and in so doing providing a second input to an XOR gate. (The first input of the XOR gate being the output of feedback loop 215 at that point.) If there is no second input provided to the XOR gate, the state of the feedback loop is not altered by that XOR gate. In this manner the LFSR can be configured as needed, preferably when the receiver is authorized or registered with the receiver, as appropriate to the environment. In other embodiments (not shown), the receiver may be fabricated for only one scrambling polynomial configuration, or at least have more limited configuration flexibility than is represented in FIG. 5. There is certainly no requirement that taps and XOR gates be present if they are not needed for a particular implementation.

(36) Note that the PRBS generated by the sending device (see FIG. 1) is normally generated by an LFSR characterized by a polynomial, and the LFSR of the receiver will normally be characterized in the same or some complimentary fashion.

(37) In the embodiment of FIG. 5, descrambler also includes an input selector 205 that determines the input to the (first register of the) LFSR 210. Input selector 205 selects the input from one of two possible sources at the direction of a control signal sel.sub.in. The first source, or input 0, is the feedback loop 215 of the LFSR 210. The second source, or input 1, is the allocated bit stream as it is received at the descrambler 200 (typically from the decimator). A controller 235 may be used to control the selector according to data and program instructions stored in memory device 240. Note that controller 235 and memory 240 need not be physically located in the descrambler 200 and may control the operation of other receiver components (not shown) as well.

(38) Note that as used herein, “memory” and “memory device” refer to physical data storage device that is non-transitory in the sense of being not merely a propagating signal.

(39) Finally, in this embodiment descrambler 200 includes an output XOR gate adder 225 for combining the output of the LFSR 210, which is feedback loop 215, with the allocated bit stream as it is received at the descrambler 200. The output of XOR gate 225 is the descrambled allocated bit stream, which is provided to the remainder of the receive train (not shown) of the receiver. Operation of the descrambler 200 will now be explained.

(40) FIG. 6 is a flow diagram illustrating a method 250 according to this embodiment of the present invention. Note that this method 250 is highly suitable for dynamic allocations. It is again presumed that there exists a mechanism by which the receiver is aware of its allocation for each frame and knows whenever there is a change in its allocation. For instance, this can be accomplished with dedicated header fields where each receiver has a known static header-field allocation.

(41) At START it is presumed that the components necessary for performing method 250 are available and operation according to this embodiment. In addition, it is presumed that the sender has the capability to insert additional bits in the transmission to each receiver. These additional bits, referred to herein as helper bits, are used to assist the receiver in determining the appropriate initial state for the LFSR in the descrambler. Since dynamic allocations are often used for the payload sections of the frame, the sender would be expected in many cases to have this capability. Note that the effective throughput to the receiver is not greatly affected as usually only a small number of additional bits are needed.

(42) The process then begins with the insertion of helper bits (step 255) into the interleaved frame (or during the interleaving process). Presuming that an m-bit LFSR is used at the scrambler of the sending device (and descrambler of the receiver), the sending device inserts m bits with value 0 at the beginning of the payload for each receiver. To be specific, these m bits are inserted exactly in the allocation for each receiver i, that is, at intervals of K.sub.i bits starting at position S.sub.i. In this embodiment, helper bits are inserted in the payload for all receivers in every transmitted frame. This bit-interleaved frame is then provided to the scrambler for scrambling (step 260), and the scrambled bit stream is then transmitted (step 265).

(43) In the embodiment of FIG. 6, the scrambled bit stream with helper bits included in the interleaved frame is received (step 270) at the receiver. In accordance with the present invention, the received bit stream is then provided to a decimator where it is decimated (step 275) to produce the allocated bit stream for the receiver, which in this embodiment includes at the beginning of the inserted m helper bits.

(44) In this embodiment, when the payload section of a frame of the allocated bit stream is received in the descrambler, it is first used to initialize the LFSR. This can be accomplished, for example, by operation (not separately shown) of an input selector, such as the input selector 205 shown in FIG. 5. If the input selector is controlled to select the input 1 for m clock cycles, then the first m bits of the allocated bit stream payload, the helper bits, are loaded into registers 1 through m of LFSR 210. After initialization, the input selector 205 is controlled to select input 0, which selects the output of feedback loop 215 for input to register 1. Note that in this embodiment, the initialization step is performed for the payload of every frame.

(45) In the embodiment of FIG. 6, the received allocated bit stream is then descrambled (step 285). Referring again to FIG. 5, this may be done by XOR adding the output of the feedback loop 215 with the allocated bit stream. The descrambled allocated bit stream may then be provided (step 290) to the remainder of the receive chain for further processing (not shown). Note, however, that in this embodiment the first m bits of each frame of the descrambled allocated bit stream (corresponding to the m helper bits) are discarded or ignored.

(46) Note that this first embodiment may be used to advantage when the PRBS generated by the scrambler in the sending unit is an MLS (maximal length sequence) and K.sub.i is a power of 2. It is a property of the PRBS that when K.sub.i is a power of 2, the decimated MLS can be generated using the same LFSR as in the scrambler with an appropriate initialization. This property is applied in a novel manner in the present invention.

(47) For convenience, the properties of this type of PRBS are reviewed here considering an m-bit LFSR where the active taps in the feedback path are determined by the recurrence relationship that the PRBS follows. If x.sub.0, . . . , x.sub.m−1 is the first m bits of the PRBS, that is the LFSR registers are initialized as Register 1=x.sub.m−1, Register 2=x.sub.m−2, . . . , Register m=x.sub.0, the recurrence is given by

(48) $x_m=\underset{j=0}{\overset{m-1}{.Math.}}{g}_j{x}_j,\mathrm{where}{g}_j\in \left\{0,1\right\}.$
The recurrence is alternately described by the generator polynomial g(X) given by

(49) $g\left(X\right)=\underset{j=0}{\overset{m}{.Math.}}{g}_j{X}^j,\mathrm{where}{g}_m=1.$
The coefficients g.sub.j determine the active taps. In the embodiment of FIG. 6, when the sender inserts helper bits in a frame, the first m bits arriving at receiver i are exactly the first m bits of the decimated MLS corresponding to receiver i. The first m bits also provide additional information. They give the initial state of the LFSR in order to generate the decimated MLS for receiver i beginning with these m bits.

(50) Again, however, when the helper bits are used to initialize the LFSR, the first m bits of the LFSR output need to be skipped because they are not needed to descramble the received data. So, the LFSR output after the XOR gates in the feedback path is used as it has the same effect of skipping the first m output bits.

(51) Note that for the helper bits, instead of inserting m 0s, the sender can also insert any m-bit string that is also known to the receiver. In this case, the receiver XORs the first m received bits with the known string to obtain the initialization (not shown).

(52) Second Embodiment

(53) The second embodiment is in many respects similar to the first, and may also be used to advantage when the PRBS generated by the scrambler in the sending unit is an MLS (maximal length sequence) and K.sub.i is a power of 2. It is also highly suitable for dynamic payload allocations. This embodiment, however, addresses an implementation where helper bits are inserted in the payload for a receiver i in the current frame only if the dynamic allocation to receiver i changes in the current frame with respect to the previous frame.

(54) FIG. 7 is a schematic diagram illustrating a descrambler 300 according to an embodiment of the present invention. It is noted that the descrambler 300 is similar or identical in many respects to the descrambler 200 shown in FIG. 5. For convenience therefore identical components are numbered identically and are not described again here unless necessary to illustrate the distinctions.

(55) More specifically, the descrambler 300 of FIG. 7 includes, in addition to those common elements depicted in FIG. 5, an output selector 230. Output selector 230 determines the output of LFSR 210 that will be used for descrambling the received allocated bit stream. Output selector 230 selects the output from one of two possible sources at the direction of a control signal sel.sub.out. The first source, or input 0, is the output of the m.sup.th register of LFSR 210, and the second source, or input 1, is the output of feedback loop 215.

(56) The XOR gate adder 225 of FIG. 7 therefore combines the output of output selector 230 with the allocated bit stream as it is received at the descrambler 200. The output of XOR gate 225 is the descrambled allocated bit stream, which is provided to the remainder of the receive train (not shown) of the receiver.

(57) Operation of the descrambler 300 in this embodiment generally follows that shown in FIG. 6, with the following alterations (not shown). At step 255 helper bits are inserted in the payload for receiver i in the current frame only if the dynamic allocation (of the payload) to receiver i changes in the current frame with respect to the previous frame. The input and output selectors are controlled accordingly, as noted in FIG. 7.

(58) Again, it is presumed that the receiver knows its allocation with respect to the payload, for example from the header portion of a frame. It can therefore detect in which frames there is a change in its dynamic (payload) allocation. This is sometimes made even easier by the presence of a dedicated bit in the header to indicate the allocation change.

(59) In this embodiment, when the payload section of a frame of the allocated bit stream is received in the descrambler 300, it is first used to initialize the LFSR only when there has been a change in the allocation. Again, this can be accomplished, for example, by operation (not separately shown) of an input selector, such as the input selector 205 shown in FIG. 7. If the input selector is controlled to select the input 1 for m clock cycles, then the first m bits of the allocated bit stream payload, the helper bits, are loaded into registers 1 through m of LFSR 210. After initialization, the input selector 205 is controlled to select input 0, which selects the output of feedback loop 215 for input to register 1. Note that in this embodiment, the initialization step is performed for the payload of every frame. Controller 235 may be used to control the selectors according to data and program instructions stored in memory device 240. Note that controller 235 and memory 240 need not be physically located in the descrambler 300 and may control the operation of other receiver components (not shown) as well.

(60) Finally, the output sequence of feedback loop 215 is selected by output selector 230 if the dynamic allocation changes in the current frame. As with the embodiment of FIG. 6, the first m bits of the descrambled data for the current frame payload are ignored, but only in this case as they correspond to the helper bits. On the other hand, if there is no change in the dynamic allocation, the output sequence of register m of the LFSR 210 is chosen. Note that where the helper bits are not used to initialize the descrambler, it may be initialized from values stored in memory, for example, using the same initialization values as the previous frame, or according to another method.

(61) Note again that this second embodiment, like the first, may also be used to advantage when the PRBS generated by the scrambler in the sending unit is an MLS (maximal length sequence) and K.sub.i is a power of 2.

(62) Third Embodiment

(63) This embodiment is highly suitable for static allocations. Initially, in this embodiment it is presumed that each receiver i=1, . . . , N has a known static allocation (S.sub.i, T.sub.i, K.sub.i), where K.sub.i is a power of 2, and that the initial state of the LFSR in the scrambler is a fixed and known m-bit sequence. This is true, for example, for some existing standards such as GPON (gigabit PON). Finally, it is presumed that each receiver has an ID (typically in binary format) that is programmed into its hardware. For example, using a simple representation where receiver i has its ID given by i−1 in binary format, each receiver has an ID of length ceil(log.sub.2/N) bits. Under these conditions, an efficient descrambler may be configured as follows.

(64) Reference is made here to FIG. 13. FIG. 13 is a schematic diagram illustrating a descrambler 320 according to an embodiment of the present invention. It is noted that the descrambler 320 is similar or identical in many respects to the descrambler 200 shown in FIG. 5. For convenience therefore identical components are numbered identically and are not described again here unless necessary to illustrate the distinctions.

(65) More specifically, the descrambler 320 of FIG. 13 includes, in addition to those common elements depicted in FIG. 5, an input selector associated with each register of the LFSR 330. Each input selector 205.sub.1 through 205.sub.m may select between one of two inputs. A first input, input 0, selects for input to the associated register the same input as would obtain in, for example, LFSR 210 of FIG. 5. Specifically if input 0 is selected each register receives on the next clock pulse the contents of the preceding register (except Register 1, which receives input from feedback loop 215. The second input, input 1, is from initialization unit 335, the operation of which will be described below. Note that in this embodiment, each input selector 205.sub.1 through 205.sub.m is provided with the same sel.sub.in control signal at the same time, which is preferably the case. Note also that although each input selector 205.sub.1 through 205.sub.m has one input connected to the initialization unit 335, the bit provided to each input selector 205.sub.1 through 205.sub.m does not necessarily have the same value.

(66) In this embodiment, some processing is performed initially and offline, that it, before the transmission of interleaved data occurs. Given a scrambling polynomial and its initial state, the following processing is performed offline: 1. The m-bit LFSR used by the scrambler (not shown) is simulated or emulated (for example by executing stored software program instructions) with the given initial state to collect the bits x.sub.0.sup.(i), . . . , x.sub.m−1.sup.(i) at positions S.sub.i, S.sub.i+K.sub.i, . . . , S.sub.i+(m−1)K.sub.i respectively from the generated sequence for each receiver i=1, . . . , N. The collected bits x.sub.0.sup.(i), . . . , x.sub.m−1.sup.(i) are the first m bits of the decimated MLS corresponding to the allocation of receiver i. 2. An initialization unit, for example initialization unit 335 shown in FIG. 13, which takes the receiver ID as input (typically in binary format) and outputs the first m bits of the decimated MLS corresponding to that receiver (found from step 1, immediately above) is designed. This can be implemented using a look-up table or combinational logic.

(67) In a related embodiment, processing above can alternately be performed mathematically instead of simulation. For each receiver i=1, . . . , N, determine the first m bits x.sup.(i)=x(S.sub.i, K.sub.i)=(x(S.sub.i, K.sub.i).sub.0, . . . , x(S.sub.i, K.sub.i).sub.m−1).sup.T of the decimated MLS for receiver i by computing
x.sup.(i)=x(S.sub.i, K.sub.i)=H.sub.s.sub.i.sub.,K.sub.i x,  (8)
where H.sub.s.sub.i.sub.,K.sub.i is an m×m matrix which depends on the starting position S.sub.i and decimation factor K.sub.i and x denotes the first m bits of the original MLS. The matrix H.sub.S.sub.i.sub.,K.sub.i is calculated as follows. Let α be a root of the polynomial g(X) as in equation (4) (See below, fifth embodiment). Using equation (4), we first compute an expression for α.sup.Si+j Ki, j=0, 1, . . . , m−1, in terms of α.sup.l, l=0, 1, . . . , m−1 to obtain

(68) $\begin{array}{cc}{\alpha }^{S_i+j{K}_i}=\underset{l=0}{\overset{m-1}{.Math.}}{h}_{j,l}{\alpha }^l\mathrm{for}l=0,1\mathrm{.Math.},m-1.& \left(9\right)\end{array}$
Next, obtain H.sub.S.sub.i.sub.,K.sub.i by taking the jth row of the matrix to contain the entries h.sub.j,0, . . . h.sub.j,m−1, where the m rows of H.sub.S.sub.i.sub.,K.sub.i are numbered j=0, 1, . . . , m−1.

(69) Note that in this embodiment, there is no change in the sender operation. It does not need to insert any bits as in embodiments one and two described above. This is very advantageous because static allocations are normally used in header fields where it would either be impossible or would be unreasonable to insert additional bits as headers are relatively very short compared to the payload.

(70) In operation, the receiver descrambler implementation is very similar to the scrambler and uses the same LFSR as in the scrambler. The only difference is in the initialization of the LFSR in the descrambler. Instead of using a fixed m-bit sequence as in the scrambler, the descrambler employs the initialization unit designed during offline processing to find the initial state of the LFSR as shown in FIG. 13. 1. The ID of the receiver is programmed, that is, stored in its hardware, for example in memory 240 shown in FIG. 13 or in another location. The receiver ID is fed as input to initialization unit. The first m bits x.sub.0, . . . , x.sub.m−1 of the decimated MLS corresponding to the receiver are obtained as the output. 2. These m bits are used to initialize the LFSR in the descrambler, for example LFSR 330 of descrambler 320. The same initial state is also used for the following frames as the allocation is static.
Thus, after initially powering ON the receiver, the initialization unit does not have any dynamic power consumption once the initial state is determined.

(71) Note also that this third embodiment, like the first two, may also be used to advantage when the PRBS generated by the scrambler in the sending unit is an MLS (maximal length sequence) and K.sub.i is a power of 2.

(72) Fourth Embodiment

(73) This method is highly suitable for static and regular allocations. As described above, a static and regular allocation is a special case of static allocations In this embodiment it is presumed that the decimation factor K for the static-regular allocation is a power of 2, and that the initial state of the LFSR in the scrambler is a fixed and known m-bit sequence as is currently true for some standards such as GPON. Finally, it is presumed that each receiver has an ID (typically in binary format) which is programmed into its hardware. For example, using a simple representation where receiver i has its ID given by i−1 in binary format, each receiver has an ID of length ceil(log.sub.2N) bits. Under these conditions, we can design an efficient descrambler as follows.

(74) In this embodiment, some processing is performed initially and offline, that it, before the transmission of interleaved data occurs. Given a scrambling polynomial and its initial state, the following processing is performed offline: 1. The m-bit LFSR used by the scrambler (not shown) is simulated or emulated (for example, by executing stored software program instructions) to collect the bits x.sub.0.sup.(i), . . . , x.sub.m−1.sup.(i) at positions S.sub.i, S.sub.i+K.sub.i, . . . , S.sub.i+(m−1)K.sub.i respectively from the generated sequence for each receiver i=1, . . . , N. The collected bits x.sub.0.sup.(i), . . . , x.sub.m−1.sup.(i) are the first m bits of the decimated MLS corresponding to the allocation of receiver i. Note that, instead of simulation or emulation, this step can also be performed by applying the mathematical equations (8) and (9) as explained above. 2. The m-bit scrambler LFSR is re-initialized to the given initial state. The LFSR is again simulated in software to find for each receiver i=1, . . . , N, the position p.sup.(i) in the generated sequence where the m-bit pattern x.sub.0.sup.(i), . . . , x.sub.m−1.sup.(i) occurs. Then, the phase shift corresponding to receivers i=1, . . . , N is computed as p.sup.(i)−1. 3. A phase shift computation unit (also not shown) which takes the receiver ID as input (typically in binary format), and outputs the phase shift corresponding to that receiver (found from step 2, immediately above) is designed. This can be implemented using a look-up table or combinational logic.

(75) Note that again in this embodiment, there is no change in the sender operation. It does not need to insert any bits as in embodiments one and two described above. This is very advantageous because static allocations are normally used in header fields where it would either be impossible or would be unreasonable to insert additional bits as headers are relatively very short compared to the payload

(76) In operation, the descrambler implementation is similar to the scrambler and uses the same LFSR as in the scrambler. The only difference is in the initialization of the LFSR in the descrambler. Instead of using a fixed m-bit sequence as in the scrambler, the descrambler computes the initial state corresponding to the receiver ID with the help of the phase shift computation unit designed during offline processing. The receiver operation is summarized in the flowchart in FIG. 14. FIG. 14 is a flow diagram illustrating a method 350 according to this embodiment of the present invention. In this embodiment, 1. The ID of the receiver is programmed, that is, stored in its hardware. The receiver ID is fed as input (step 355) to the phase shift computation unit. The phase shift of the decimated MLS corresponding to the receiver with respect to the original MLS (from the scrambler) is obtained as the output (step 360). 2. The LFSR in the descrambler is initialized to the fixed and known m-bit sequence used by the scrambler. The LFSR is then run for a number of cycles (step 365) equal to the phase shift. The state of the LFSR after so many cycles is then saved (step 370). Note that steps 1 and 2 as described here are performed only once after turning ON the receiver (and not for every frame). 3. The saved LFSR state is used as the initial state (not shown in FIG. 14) in the descrambler for every frame. Since the allocation is static, the initialization remains the same for all frames.

(77) Note that there may be a delay in running the descrambler for a number of cycles equal to the phase shift (that is, step 365 of FIG. 14, which is step 2 immediately above). For this reason immediately after powering ON the receiver, typically the first received frame (or the first few frames in the worst-case) may be lost. Fortunately, this is not a big concern as this computation does not need to be repeated while the receiver is ON. Note also that the method of this embodiment can also be used in combination with the fifth embodiment described below. Specifically, it is possible to shorten the delay in step 2 (immediately above; step 365 of FIG. 14) by using a scrambling method that skips states (such as in embodiment 5, below). Using such an approach, the scrambler can skip states to quickly compute the state of the LFSR after the number of cycles given by the phase shift.

(78) It is noted that the third and fourth embodiments are similar. It would be expected that the third embodiment has lower power consumption than this one (the fourth embodiment). However, this embodiment may potentially have an area benefit compared with the third embodiment if it is designed intelligently. The initial state of the scrambler, for example, can be picked intelligently so as to make the phase shift computation unit very simple. This can be accomplished by a simple trial and error method where the preprocessing steps are repeated for different scrambler initial states until a simple relationship between the receiver ID and phase shift is found. This is illustrated below. In this case, since the phase shift computation is simple and the remaining part of the initialization is accomplished using the same LFSR, there can be a potential savings in chip area.

(79) The following examples 1 and 2 illustrate some sample results from the preprocessing stage. In the examples below, the starting position S.sub.i=i and the receiver ID is i−1 for each of the receivers i=1, . . . , N. The decimation factor K is the same as the number of receivers N. The phase shift corresponding to each receiver ID is computed using software simulations. These results are then used to derive a mathematical relationship between the phase shift and receiver ID. This mathematical formula can then be used to design the phase shift computation unit.

EXAMPLE 1

(80) Presume that N=K=32 and the scrambling polynomial (i.e., the polynomial which specifies the length and taps of the LFSR used by the scrambler) is 1+x.sup.6+x.sup.7. Note that this is the same scrambling polynomial that is used by GPON. If the initial state of the scrambler is all 1s, i.e., Register 1=1, . . . , Register 7=1, as specified by GPON, then the corresponding relationship between the receiver ID and the phase shift is given in FIG. 8. Observe that this is a piece-wise linear relationship and it can be described mathematically in several ways. For example, we can use either
Phase shift=2.sup.2×Receiver ID+109 if Receiver ID<=4,
2.sup.2×Receiver ID−18 if Receiver ID>=5,
or
Phase shift=(2.sup.2×Receiver ID+109) mod (2.sup.7−1),
to describe the relationship in FIG. 8. Depending on the hardware resources available, one of these may be simpler to implement than the other.

(81) On the other hand, by experimenting with different initial states for the scrambler, we can find a much simpler relationship between the receiver ID and phase shift. If the scrambler initial state is set as [0, 0, . . . , 0, 1], i.e., Register 1=0, Register 2=0, . . . , Register 7=1, then the corresponding relationship between the receiver ID and the phase shift is given in FIG. 9. Observe that this is a simple linear relationship and it can be easily described mathematically as
Phase shift=2.sup.2×Receiver ID.
The multiplication of the receiver ID by a power of 2 can be easily implemented in hardware by a simple left shift operation. Therefore, we obtain a very simple implementation of the phase shift computation unit.

EXAMPLE 2

(82) Suppose that N=K=256 and the scrambling polynomial (i.e., the polynomial which specifies the length and taps of the LFSR used by the scrambler) is 1+x.sup.18+x.sup.23. If the initial state of the scrambler is all 1s, i.e., Register 1=1, . . . , Register 23=1, then the corresponding relationship between the receiver ID and the phase shift is given in FIG. 10. Observe that this is a piece-wise linear relationship and it can be described mathematically in several ways. For example, we can use either
Phase shift=2.sup.15×Receiver ID+5615754 if Receiver ID<=84,
2.sup.15×Receiver ID−2772853 if Receiver ID>=85,
or
Phase shift=(2.sup.2×Receiver ID+109) mod (2.sup.7−1),
to describe the relationship in FIG. 10. Depending on the hardware resources available, one of these may be simpler to implement than the other.

(83) On the other hand, by experimenting with different initial states for the scrambler, we can find a much simpler relationship between the receiver ID and phase shift. If the scrambler initial state is set as [0, 0, . . . , 0, 1], i.e., Register 1=0, Register 2=0, . . . , Register 23=1, then the corresponding relationship between the receiver ID and the phase shift is given in FIG. 11. Observe that this is a simple linear relationship and it can be easily described mathematically as
Phase shift=2.sup.15×Receiver ID.
The multiplication of the receiver ID by a power of 2 can be easily implemented in hardware by a simple left shift operation. Therefore, we obtain a very simple implementation of the phase shift computation unit.

(84) Note that if the initial state of the scrambler is not fixed, then the method of the fourth embodiment may be modified at the cost of some additional complexity. In the offline processing stage, simulations or emulations can be used to design a phase shift computation unit that takes both the receiver ID and the scrambler initial state as inputs, and outputs the phase shift of the decimated MLS corresponding to the receiver and scrambler initialization.

(85) Finally, note that in this fourth embodiment, to compute the initialization the phase shift corresponding to each receiver is computed in preprocessing, that is, offline. Once the phase shift is known, the correct initialization to generate the decimated MLS can be found by using the scrambler initial state in the LFSR and running the LFSR for a number of cycles equal to the phase shift. Using the LFSR state after so many cycles as the initial state at the descrambler, we generate the same MLS with the correct phase shift, i.e., we generate exactly the decimated MLS as needed. This embodiment is suitable for implementations where the decimation factor K for all receivers is a power of 2, since the decimated MLS in this case for each receiver is the same as the original MLS except for a phase shift. Therefore, the decimated MLS can be generated using the same LFSR as in the scrambler with an appropriate initialization.

(86) Fifth Embodiment

(87) As background for this embodiment and the two that follow, recall that the descrambling methods previously described may be used where (a) the PRBS used by the scrambler is a maximal length sequence (MLS); and (b) at any receiver i where the decimation factor K.sub.i is a power of 2.

(88) Although these conditions are inherently true in many situations, or the system may be designed such that they are true, there remains the possibility that we can be forced to a situation where at least one of the above conditions is not true. The method proposed in this embodiment does not impose or rely on any of these above conditions (a) or (b). This advantage, however, comes at the price of relatively higher complexity. Furthermore, the method of this embodiment may be used in combination with the previously described fourth embodiment.

(89) The state of the descrambler is given by the vector r=(r.sub.m, . . . r.sub.1) where r.sub.i is the bit value stored in register i. Indeed, given the state is r, the first m bits generated by the LFSR are exactly (x.sub.0, . . . , x.sub.m−1)=(r.sub.m, . . . , r.sub.1).

(90) First, a method is described to implement a descrambler that skips a fixed number S states ahead from the current state (with respect to the original LFSR in the scrambler) during each clock cycle. Note that S is not necessarily a power of 2, and the LFSR used in the scrambler can generate any PRBS, which is not necessarily an MLS. The general implementation of the skipping descrambler is shown in FIG. 12. As should be apparent, each of the Logic units 1 though m respectively updates individual registers 1 through m after processing information collected from each register. The logic used for determining the descrambler state S cycles ahead from the current state is found using the following offline processing steps. 1. Take the original m-bit LFSR used by the scrambler. For each of the initial states e.sub.1, . . . , e.sub.m, where e.sub.i is the initial state where register i is 1 and the remaining registers are 0, the m-bit state
r(e.sub.i, S)=(r.sub.m(e.sub.i, S), . . . , r.sub.1(e.sub.i, S))  of the descrambler after S cycles is found using simulation or emulation. 2. The transfer function/matrix for computing the descrambler state S cycles ahead as a function of its current state is obtained as follows:

(91) $C_S=\left[\begin{array}{cccc}{r}_m\left(e_m,S\right)& r_m\left(e_{m-1},S\right)& \mathrm{.Math.}& r_m\left(e_1,S\right)\\ r_{m-1}\left(e_m,S\right)& r_{m-1}\left(e_{m-1},S\right)& \mathrm{.Math.}& r_{m-1}\left(e_1,S\right)\\ \mathrm{.Math.}& \ddots & \ddots & \mathrm{.Math.}\\ r_1\left(e_m,S\right)& r_1\left(e_{m-1},S\right)& \mathrm{.Math.}& r_1\left(e_1,S\right)\end{array}\right].$  Consequently, if the current state of the descrambler is r=(r.sub.m, . . . , r.sub.1).sup.T, the new descrambler state r′=(r′.sub.m, . . . , r′.sub.1).sup.T after S cycles can be obtained as
r′=C.sub.S r. 3. The logic for implementing the state skipping is then determined from C.sub.S. Such implementation is possible in several ways. As an example, the new descrambler state r′=(r′.sub.m, . . . , r′.sub.1).sup.T after S cycles from the current state r=(r.sub.m, . . . , r.sub.1).sup.T can be computed as follows:

(92) $r_i^{\prime }=\underset{\underset{c_{i,m-j+1}=1}{j=1,\mathrm{.Math.},m\text{:}}}{\oplus }{r}_{j,}$$i=1,\mathrm{.Math.},m,$  where c.sub.ij, with i,j=1, . . . , m, is the entry in C.sub.S in row i and column j.
Note that the matrix C.sub.S in step 2 above can alternately be calculated mathematically using equations (2) and (5) of the following:
It is possible to compute the special cases: (a) x(S, 1) i.e., the first m bits of the MLS starting at position S and taking every bit (i.e., no decimation) of the original MLS; and (b) x(0, K) i.e., the first m bits of the MLS that is decimated by factor K starting from the first bit. The equations have the following structure:
x(S, 1)=C.sub.S x,  (2)
x(0, K)=D.sub.K x,  (3)
where C.sub.S and D.sub.K are m×m matrices which depend on the starting position S and decimation factor K respectively. The matrices C.sub.S and D.sub.K are calculated as follows. Let α be a root of the polynomial g(X). Then, we have

(93) $\begin{array}{cc}{\alpha }^m=\underset{j=0}{\overset{m-1}{.Math.}}{g}_j{\alpha }^j.& \left(4\right)\end{array}$
To compute C.sub.S: First, we use equation (4) to compute an expression for α.sup.S+j, j=0, 1, . . . , m−1, in terms of α.sup.l, l=0, 1, . . . , m−1 to obtain

(94) $\begin{array}{cc}{\alpha }^{S+j}=\underset{l=0}{\overset{m-1}{.Math.}}{c}_{j,l}{\alpha }^l\mathrm{for}j=0,1,\mathrm{.Math.},m-1.& \left(5\right)\end{array}$
Further, C.sub.S may be obtained by taking the jth row of the matrix to contain the entries c.sub.j,0, . . . , c.sub.j,m−1, where the m rows of C.sub.S are numbered j=0, 1, . . . , m−1.
And to compute D.sub.K: First, use equation (4) to compute an expression for α.sup.jK,j=0, 1, . . . , m−1, in terms of α.sup.l, l=0, 1, . . . , m−1 to obtain

(95) $\begin{array}{cc}{\alpha }^{jK}=\underset{l=0}{\overset{m-1}{.Math.}}{d}_{j,l}{\alpha }^l\mathrm{for}j=0,1,\mathrm{.Math.},m-1.& \left(6\right)\end{array}$
Next, obtain D.sub.K by taking the jth row of the matrix to contain the entries d.sub.j,0, . . . , d.sub.j,m−1, where the m rows of D.sub.K are numbered j=0, 1, . . . , m−1.

(96) Also note the following. If the recurrence relation for the LFSR is given by construct the m×m matrix G as follows: ′

(97) $G=\left[\begin{array}{cccc}& & & \\ 0_{m-1}& & I_{m-1}& \\ & & & \\ g_0& g_1& \mathrm{.Math.}& g_{m-1}\end{array}\right],$
where 0.sub.m−1 is the column vector with m−1 zeros and l.sub.m−1 is the (m−1)×(m−1) identity matrix. Then, C.sub.S can also be computed using the relation
C.sub.S=G.sup.S.
Sixth Embodiment

(98) This embodiment is related to the fifth, described above. The method proposed in this embodiment does not impose or rely on the conditions (a) the PRBS used by the scrambler is a maximal length sequence (MLS); or (b) where the decimation factor K.sub.i is a power of 2. This advantage, however, again comes at the price of relatively higher complexity. Furthermore, the method of this embodiment may be used in combination with the previously described fourth and fifth embodiments.

(99) The state of the descrambler is again given by the vector r=(r.sub.m, . . . r.sub.1) where r.sub.i is the bit value stored in register i. Indeed, given the state is r, the first m bits generated by the LFSR are exactly (x.sub.0, . . . , x.sub.m−1)=(r.sub.m, . . . , r.sub.1).

(100) In this embodiment a method is proposed for skipping a variable number of cycles ahead. Initially, presume the descrambler required to skip a variable number S states ahead from the current state. Suppose that S can be any value that is at most S.sub.max (given). The trivial way is of course to implement the logic for fixed skipping for each S that is at most S.sub.max and use one of them as desired. The method of this embodiment is believed to be more efficient and is proposed below. 1. The number of bits to represent S.sub.max in binary format is computed as p=ceil(log.sub.2(S.sub.max+1)). 2. The logic for skipping a fixed number of cycles ahead is implemented for every S′=2.sup.i, where i=0, 1, 2, . . . , p−1. This logic may be based on the fifth embodiment, above, but can be based on other schemes as well. 3. In order to skip S cycles ahead, where S is at most S.sub.max, a combination of the fixed skipping logic in step 2 are cascaded as needed. This is achieved by taking the binary representation of S and cascading the logic corresponding to S′=2.sup.i if the bit position i (with least significant bit having position 0) in the binary representation of S is 1. This is shown in FIG. 15. FIG. 15 is a schematic that illustrates a descrambler that skips states by a variable number S=(b.sub.p−1, b.sub.p−2, . . . b.sub.0) of cycles ahead, where (b.sub.p−1, b.sub.p−2, . . . b.sub.0) denotes the binary representation of S.

(101) As an example, presume S.sub.max=250. Then, p=ceil(log.sub.2(251))=8. In this case, the logic for skipping 1, 2, 2.sup.2, . . . , 2.sup.7 cycles are each implemented. Suppose we wish to skip S=200 cycles ahead at some point. The binary representation for 200 is given by 11001000. So, skipping 200 cycles ahead is accomplished by cascading the logic for skipping ahead by 2.sup.7, 2.sup.6 and 2.sup.3 cycles.

(102) Note that minor variations of steps 2 and 3, immediately above, are possible. For example, instead of implementing the logic skipping for 2.sup.i cycles separately, this can also be done by skipping 2.sup.i−1 cycles twice. Other variations are possible based on the decomposition property (see equation 11, below; eighth embodiment), as will be explained below in further detail.

(103) Seventh Embodiment

(104) This embodiment is related to the fifth and sixth, described above. The method proposed in this embodiment does not impose or rely on the conditions (a) the PRBS used by the scrambler is a maximal length sequence (MLS); or (b) where the decimation factor K.sub.i is a power of 2. This advantage, however, again comes at the price of relatively higher complexity. Furthermore, the method of this embodiment may be used in combination with the previously described fourth, fifth, and sixth embodiments.

(105) The state of the descrambler is again given by the vector r=(r.sub.m, . . . r.sub.1) where r.sub.i is the bit value stored in register i. Indeed, given the state is r, the first m bits generated by the LFSR are exactly (x.sub.0, . . . , x.sub.m−1)=(r.sub.m, . . . , r.sub.1).

(106) In this embodiment a method is proposed for descrambling bit-interleaved traffic. Initially, suppose the allocation for receiver i is (S.sub.i, T.sub.i, K.sub.i). In order to produce the bits for descrambling receiver i's allocation, use the method for skipping a variable number of cycles as follows: 1. The registers are initialized to the original initial state used by the scrambler. 2. As outlined in the sixth embodiment, the logic for skipping a fixed number of cycles ahead is implemented for every S′=2.sup.i, where i=0, 1, 2, . . . , p−1. We can set S.sub.max for example as S.sub.max=max (S.sub.i, K.sub.1, . . . , S.sub.N, K.sub.N). 3. The logic to skip ahead by S.sub.i cycles is activated once (by cascading) to obtain the initial state corresponding to receiver i. This initial state is stored and is used directly for future frames. For static allocations, this computation is done only once. For dynamic allocations, the initial state is updated whenever there is a change in S.sub.i. 4. After initializing to the state corresponding to S.sub.i, the logic to skip ahead by K.sub.i cycles is activated continuously (by cascading) to produce the bits needed to descramble the traffic obtained by receiver i. See FIG. 15.
Eighth Embodiment

(107) As background to the eighth embodiment, suppose an m-bit LFSR is used in the scrambler and consider a receiver i with allocation (S.sub.i, T.sub.i, K.sub.i) where K.sub.i is a power of 2. In order to produce the decimated MLS corresponding to receiver i using the same LFSR, it needs to be initialized appropriately.

(108) The appropriate initialization of the LFSR is given by the first m bits x(S.sub.i, K.sub.i)=(x(S.sub.i, K.sub.i).sub.0, . . . , x(S.sub.i, K.sub.i).sub.m−1).sup.T of the decimated MLS for receiver i. This can be mathematically computed as x(S.sub.i, K.sub.i) using equations (8) and (9), above. These computations depend on the allocation parameters S.sub.i, K.sub.i, but it is manageable if the allocations are static. However, if S.sub.i and K.sub.i vary dynamically, a practical method to perform the computations is desirable.

(109) This embodiment outlines how such an initialization unit can be designed for dynamic allocations. The function of the initialization unit in a descrambler according to this embodiment is shown in FIG. 16. FIG. 16 is a schematic diagram illustrating a descrambler 400 according to an embodiment of the present invention. It is noted that the descrambler 400 is similar or identical in many respects to the descrambler 330 shown in FIG. 13. For convenience therefore identical components are numbered identically and are not described again here unless necessary to illustrate the distinctions. In the embodiment of FIG. 16, initialization unit 420 takes the original initial state (corresponding to the first m bits x of the original MLS), S.sub.i and K.sub.i as inputs, and outputs the appropriate initialization to produce the decimated MLS.

(110) First, observe that the following property is true:
x(S.sub.i, K.sub.i)=H.sub.S.sub.i.sub.,K.sub.ix=D.sub.K.sub.iC.sub.S.sub.ix,  (10)
where D.sub.Ki and C.sub.Si are determined by equations (2)-(6). This is because x′=C.sub.Si x provides the first m bits of the MLS starting at position S.sub.i. Now, considering the MLS starting with x′ (i.e., at position S.sub.i of the original MLS), computing D.sub.Ki x′ provides the first m bits of the MLS decimated by factor K.sub.i. Thus, equation (10) provides a decomposition of the computation where C.sub.Si accounts for skipping the first S.sub.i positions and D.sub.Ki accounts for the decimation by factor K.sub.i.

(111) In general, the logic for multiplying a binary m×m matrix A by a binary vector x=(x.sub.0, . . . , x.sub.m−1).sup.T
x′=A x
is simple to implement and this is possible in several ways. As an example

(112) 0$x_i^{\prime }=\underset{\underset{a_{i,j}=1}{j=1,\mathrm{.Math.},m\text{:}}}{\oplus }{x}_j,i=1,\mathrm{.Math.},m,$
where a.sub.ij, with i,j=1, . . . , m, is the entry in A in row i and column j. The main problem in the implementation of equation (10) is that S.sub.i and K.sub.i can vary.

(113) Now, in order to support varying values of S.sub.i, the ideas described in embodiment six, above, can be used. Presume that S.sub.i can be any value that is at most S.sub.max and p=ceil(log.sub.2(S.sub.max+1)). The logic for skipping a fixed number of cycles (i.e., positions in the original MLS) ahead is implemented for every S′=2.sup.i, where i=0, 1, 2, . . . , p−1. This logic may be based on the fifth embodiment, above, but can be based on other schemes as well. In order to skip S.sub.i=(b.sub.p−1, b.sub.p−2, . . . , b.sub.0) cycles ahead, where (b.sub.p−1, b.sub.p−2, . . . , b.sub.0) denotes the binary representation of S.sub.i, a combination of the fixed skipping logic are cascaded as needed. Specifically, the logic corresponding to skipping S′=2.sup.i cycles is cascaded if b.sub.i=1.

(114) The decomposition of S.sub.i to support varying values using its binary representation as described above is quite convenient especially in hardware. More generally, the decomposition is based on the following basic property:
If S.sub.i=a+b, then C.sub.Si=C.sub.a.Math.C.sub.b where a, b are positive integers.  (11)
Based on this property, there are several possible decompositions, one of which may suit the particular application. For example, the logic for skipping a fixed number of cycles can be implemented for S′=10.sup.i, for i=0, 1, 2, . . . . Then, in order to skip, say S.sub.i=154 cycles, we call the logic for skipping S′=10.sup.2, 10.sup.1, 10.sup.0 cycles once, five times, and four times respectively in a cascade manner.

(115) In order to support varying values of K.sub.i, we use the following decomposition property which holds when K.sub.i is a power of 2:
If K.sub.i=a.Math.b with a=2.sup.a′ and b=2.sup.b′, then D.sub.Ki=D.sub.a.Math.D.sub.b.  (12)
Thus, in the simplest implementation, it is only necessary to realize the logic for D.sub.2, i.e, decimation by factor 2. Then, decimation by any K.sub.i=2.sup.k can be realized by calling the logic for D.sub.2 in a cascade manner for k times since D.sub.2^k=(D.sub.2).sup.k. In a more sophisticated implementation, the decimation logic for D.sub.K′ where K′=2.sup.x, 2.sup.y, 2.sup.z, . . . can be implemented. Then, in order to decimate by factor K.sub.1=2.sup.x+y+z, we cascade the logic for decimation by K′=2.sup.x, 2.sup.y and 2.sup.z; to decimate by factor K.sub.2=2.sup.x+y, we cascade the logic for decimation by K′=2.sup.x and 2.sup.y; and so on.
To summarize, the initialization unit of the descrambler operates in the following steps, which is also illustrated in FIG. 17. FIG. 17 illustrates an initialization unit for dynamic allocation where where S.sub.i is represented in binary by (b.sub.p−1, . . . , b.sub.0) and a.sub.q−1, . . . , a.sub.0 are binary values such that K.sub.i=(2.sup.x)^a.sub.q−1. (2.sup.y)^a.sub.q−2 . . . (2.sup.z)^a.sub.0. 1. Based on the decomposition property (11), the logic for skipping a fixed number of cycles ahead is implemented for different values of S′ as determined by the application scenario. 2. Based on the decomposition property (12), the logic for decimation by K′ is implemented for different values of K′ (which are powers of 2) as determined by the application scenario. 3. Start with the original initial state (corresponding to the first m bits x of the original MLS) which is used by the scrambler and is also known to the receiver. 4. The logic to skip ahead by S.sub.i cycles is first activated (by cascading) using the property (11) as explained above. 5. The logic for decimation by factor K.sub.i is then activated (by cascading) using the property (12) as explained above. 6. The final m bits obtained as the output is the initial state corresponding to receiver i. This initial state is stored and is used directly for future frames. For static allocations, this computation is done only once. For dynamic allocations, whenever there is a change in S.sub.i or K.sub.i, we go back to step 3 and re-calculate the appropriate initial state.

(116) Finally, the m bits output from the initialization unit are used to initialize the LFSR (which is the same as in the scrambler) to produce exactly the decimated MLS required for descrambling the data.

(117) Note that the sequences of operation illustrated in the drawings and explained herein by reference to them represent exemplary embodiments; some variation is possible within the spirit of the invention. For example, additional operations may be added to those shown, and in some implementations one or more of the illustrated operations may be omitted. In addition, the operations of the method may be performed in any logically-consistent order unless a definite sequence is recited in a particular embodiment. The same is true for the skipping logic and the decimating logic illustrated in the drawings, for example FIGS. 15 and 17, and explained in the Specification.

(118) Although multiple embodiments of the present invention have been illustrated in the accompanying Drawings and described in the foregoing Detailed Description, it should be understood that the present invention is not limited to the disclosed embodiments, but is capable of numerous rearrangements, modifications and substitutions without departing from the invention as set forth and defined by the following claims. For example, consider a sender that broadcasts the same information to all N receivers. Note that all N receivers are interested in the same information in this example. So, a broadcast scheme rather than a multiplexing scheme is used. Suppose the sender broadcasts at a high rate of, say, 10 Gbps. Further, suppose that some of the receivers can handle only smaller rates of reception, say, 1 Gbps, 2.5 Gbps etc. In this case, each such receiver obtains a set of intermittent bits from the original transmission at a rate corresponding to the receiver's limit. Once again, the receiver is faced with the problem of descrambling a set of intermittent bits. Our techniques will be applicable in this situation too.