# Patent

## Title
Bit interleaver and method of bit interleaving using the same

## Abstract

A bit interleaver and a bit interleaving method are provided. The bit interleaver includes delay devices which are applied with symbol interleaving and tone interleaving, and delay a bit stream output from a memory, to generate a delayed bit stream; a first multiplexer (MUX) unit which selects any one of a bit of the bit stream output from the memory and a bit of the delayed bit stream, to generate a selection bit stream; and a second MUX unit which changes an order of the selection bit stream to generate an output bit stream. Accordingly, it is possible to easily and effectively perform bit interleaving including a cyclic shift.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
This application claims priority from Korean Patent Application No. 10-2006-0072286, filed on Jul. 31, 2006, in the Korean Intellectual Property Office, the entire disclosure of which is incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
Methods and apparatuses consistent with the present invention relates to bit interleaving, and more particularly, bit interleaving which can satisfy a WiMedia Ultra-Wideband physical layer specification (UWB PHY spec).
2. Description of Related Art
Bit interleaving is performed so that a communication system can be robust against a burst error. Specifically, bit interleaving can acquire a frequency diversity effect in a frequency hopping method, such as a multi-band orthogonal frequency division multiplexing (MB-OFDM) scheme. In the MB-OFDM scheme, latency may be reduced by limiting bit interleaving to less than three OFDM symbols.
Here, bit interleaving of the MB-OFDM scheme includes two operations. A first operation corresponds to a symbol interleaving operation. A second operation corresponds to a tone interleaving operation.
Tone interleaving enables a frequency diversity effect to be acquired between tones in a single sub-band by scattering data in a single OFDM symbol.
As an example, when a number of coded bits per OFDM symbol is 100, symbol interleaving with respect to a bit stream containing three symbols may be represented as,
0, 1, 2, 3, 4, 5, . . . , 299
→0, 3, 6, 9, . . . , 297, 1, 4, 7, 10, . . . , 298, 2, 5, 8, 11, . . . , 299
Also, tone interleaving with respect to a result of the symbol interleaving may be represented as,
0, 3, 6, 9, . . . , 297, 1, 4, 7, 10, . . . , 298, 2, 5, 8, 11, . . . , 299
→0, 30, 60, 90, . . . , 270, 3, 33, 63, 93, . . . , 273, 6, 36, 66, 96, . . . , 276, . . . .
U.S. Patent Publication No. 20040178934 discloses in detail a symbol interleaver and a tone interleaver for performing symbol interleaving and tone interleaving respectively.
When performing only symbol interleaving and tone interleaving, interleaving may be easily performed by simply arranging input data two-dimensionally in a storage space and appropriately reading the arranged input data. However, WiMedia UWB PHY spec 1.0 performs interleaving by adding an “intra-symbol cyclic shift” function.
Specifically, WiMedia UWB PHY spec 1.0 performs symbol interleaving and tone interleaving, and also performs a cyclic shift. Thus, when simply reading a memory as in a conventional art, interleaving may not be generally performed.
Accordingly, a new type of bit interleaver and bit interleaving method which can perform bit interleaving including a cyclic shift without adding complex hardware is required.
SUMMARY OF THE INVENTION
The present invention provides a bit interleaver and a bit interleaving method which can easily and effectively perform bit interleaving including a cyclic shift.
The present invention also provides a bit interleaver and a bit interleaving method which can satisfy requirements of at least WiMedia Ultra-Wideband UWB PHY spec 1.0.
The present invention also provides a bit interleaver and a bit interleaving method which can easily perform a cyclic shift operation by using an output feature of result of symbol interleaving and tone interleaving.
According to an aspect of the present invention, there is provided a bit interleaver including: delay devices which are applied with symbol interleaving and tone interleaving and delay a bit stream outputted from a memory, to generate a delayed bit stream; a first multiplexer (MUX) unit which selects any one of a bit of the bit stream outputted from the memory and a bit of the delayed bit stream, to generate a selection bit stream; and a second MUX unit which changes an order of the selection bit stream to generate an output bit stream.
The bit interleaver may further include a register which stores a portion of bits of a previous bit stream output from the memory, a predetermined clock before the bit stream is output from the memory; and a third MUX unit which selects any one of an output of the register and a portion of output bits of the second MUX unit to generate the output bit stream.
Also, the bit stream output from the memory may correspond to indexes having an identical number in a one's column.
Also, the first MUX unit may select a bit corresponding to the delayed bit stream with respect to bits not corresponding to bits stored in the register, when selecting a bit corresponding to the bit stream output from the memory with respect to bits corresponding to the bits stored in the register among the bit stream output from the memory.
Also, the third MUX unit may generate a predetermined number of higher bits of the output bit stream by using a predetermined number of lower bits of the previous bit stream.
According to another aspect of the present invention, there is provided a bit interleaver including: delay devices which are applied with symbol interleaving and tone interleaving, and delay a portion of bits of a bit stream output from a memory to generate a delayed bit stream; a register which stores a portions of bits of a previous bit stream output from the memory, a predetermined clock before the bit stream is output from the memory; and a MUX unit which selects any one of an output of the register and bits corresponding to a bit stream, the bit stream which is not delayed by the delay devices and output from the memory, wherein the bit interleaver generates an output bit stream by using the delay devices and the output of the MUX unit.
The bit interleaving method may further include storing a portion of bits of a previous bit stream output from the memory, a predetermined clock before the bit stream is output from the memory, and replacing a portion of bits of the output bit stream with the stored bits.
According to still another aspect of the present invention, there is provided a bit interleaving method including: outputting a bit stream corresponding to a result of symbol interleaving and tone interleaving, from a memory; generating a delayed bit stream by delaying a portion of bits of the bit stream output from the memory; and generating an output bit stream by storing a portion of bits of a previous bit stream output from the memory, a predetermined clock before the bit stream is output from the memory, and replacing a portion of bits of the output bit stream with the stored bits.



BRIEF DESCRIPTION OF THE DRAWINGS
The above and other aspects of the present invention will become apparent and more readily appreciated from the following detailed description of certain exemplary embodiments of the invention, taken in conjunction with the accompanying drawings of which:
FIG. 1 is a block diagram illustrating a configuration of a transmitting side of a modem including a bit interleaver according to an exemplary embodiment of the present invention;
FIG. 2 is a table illustrating an example of a 300 bit input stored in a memory when an interleaver operates at 53.3 Mbps;
FIG. 3 is a table illustrating a result of symbol interleaving performed with respect to the 300 bit input as shown in FIG. 2;
FIG. 4 is a table illustrating a result of indicating the result of symbol interleaving as shown in FIG. 3 as index 0 to index 99;
FIG. 5 is a table illustrating a result of tone interleaving performed with respect to the result as shown in FIG. 4;
FIG. 6 is a table illustrating a result of a cyclic shift performed with respect to the result as shown in FIG. 5;
FIG. 7 is a table illustrating an output bit stream of a bit interleaver according to an exemplary embodiment of the present invention;
FIG. 8 is a table illustrating a bit stream output from a memory to generate the output bit stream as shown in FIG. 7;
FIG. 9 is a table illustrating a memory control signal applied to output a first group as shown in FIG. 8 from a memory;
FIG. 10 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to a first group as shown in FIG. 7;
FIG. 11 is a table illustrating a memory control signal applied to output a second group as shown in FIG. 8 from a memory;
FIG. 12 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to a second group as shown in FIG. 7;
FIG. 13 is a table illustrating a memory control signal applied to output a third group as shown in FIG. 8 from a memory;
FIG. 14 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to a third group as shown in FIG. 7;
FIG. 15 is a table illustrating an example of a 600 bit input stored in a memory when an interleaver operates at 106.7 Mbps or 200 Mbps;
FIG. 16 is a table illustrating a result of symbol interleaving performed with respect to the 600 bit input as shown in FIG. 15;
FIG. 17 is a table illustrating a result of indicating the result of symbol interleaving as shown in FIG. 16 as index 0 to index 199;
FIG. 18 is a table illustrating a result of tone interleaving performed with respect to the result as shown in FIG. 17;
FIG. 19 is a table illustrating a result of a cyclic shift performed with respect to the result as shown in FIG. 18;
FIG. 20 is a table illustrating an output bit stream of a bit interleaver according to an exemplary embodiment of the present invention;
FIG. 21 is a table illustrating a bit stream output from a memory to generate the output bit stream as shown in FIG. 20;
FIG. 22 is a table illustrating a memory control signal applied to generate a first group as shown in FIG. 21 from a memory;
FIG. 23 is a table illustrating a memory control signal applied to output a second group as shown in FIG. 21 from a memory;
FIG. 24 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to a second group as shown in FIG. 20;
FIG. 25 is a diagram illustrating a memory control signal applied to output a third group as shown in FIG. 21 from a memory;
FIG. 26 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to a third group as shown in FIG. 20;
FIG. 27 is a flowchart illustrating a bit interleaving method according to an exemplary embodiment of the present invention; and
FIG. 28 is a flowchart illustrating a bit interleaving method according to another exemplary embodiment of the present invention.



DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS OF THE INVENTION
Reference will now be made in detail to exemplary embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The exemplary embodiments are described below in order to explain the present invention by referring to the figures.
FIG. 1 is a block diagram illustrating a configuration of a transmitting side of a modem including a bit interleaver according to an exemplary embodiment of the present invention.
Referring to FIG. 1, a configuration of a WiMedia Wideband UWB modem includes a convolutional encoder 110, a puncturer 120, an interleaver 130, a quadrature phase shift keying (QPSK) mapper 140, and an inverse fast Fourier transformer (IFFT) 150.
The convolutional encoder 110 performs convolutional encoding of input data for error correction.
The puncturer 120 adjusts an encoding rate by punctuating an output of the convolutional encoder 110. Depending upon embodiments, at least two puncturers 120 may be provided. Also, the puncturer 120 may be omitted.
The interleaver 130 performs symbol interleaving, tone interleaving, and a cyclic shift.
Here, the interleaver 130 receives a 6 bit signal, and outputs a 10 bit signal. An output signal of the interleaver 130 is output into a predetermined format to perform QPSK mapping and IFFT.
FIG. 2 is a table illustrating an example of a 300 bit input stored in a memory when an interleaver operates in 53.3 Mbps.
Referring to FIG. 2, the memory includes 10 banks 210, 211, 212, 213, 214, 215, 216, 217, 218, and 219. Here, a bank number may be represented as j×2+i where i designates an integer of 0 or 1, and j designates an integer from 0 to 4. Specifically, the bank number is determined by i and j. As an example, when both i and j are 0, the bank number becomes 0. Also, when i is 1 and j is 2, the bank number becomes 5, and when i is 1 and j is 4, the bank number becomes 9.
Numbers as shown in FIG. 2 designate an order of input data. Specifically, number 0 to number 299 as shown in FIG. 2 designate first input data to 300th input data.
FIG. 3 is a table illustrating a result of symbol interleaving performed with respect to the 300 bit input as shown in FIG. 2.
Referring to FIG. 3, when performing symbol interleaving with respect to the 300 bit input as shown in FIG. 2, the 300 bit input data is classified into three groups. A first group 310 corresponds to a group of input data having a remainder of 0 when dividing an order of input data by 3. A second group 320 corresponds to a group of input data having a remainder of 1 when dividing an order of input data by 3, and a third group 330 corresponds to a group of input data having a remainder of 2 when dividing an order of input data by 3.
Specifically, symbol interleaving may be represented as,

S(j)=U{Floor(j/NCPBS)+3 Mod(j,NCPBS)}  [Equation 1]

Here, S( ) designates symbol interleaving, and U( ) designates input data. Also, NCPBS designates a number of coded bits per orthogonal frequency division multiplexing (OFDM) symbol. In FIG. 3, NCPBS is 100. Also, Floor( ) returns an integer that is less than a transmitted parameter, but nearest to the transmitted parameter, and Mod( ) returns a remainder of division.
FIG. 4 is a table illustrating a result of indicating the result of symbol interleaving as shown in FIG. 3 as index 0 to index 99.
Referring to FIG. 4, each of the first group 310, the second group 320, and the third group 330 as shown in FIG. 3 is indicated as index 0 to index 99.
Here, the quotient, acquired by dividing an order of input data by 3, is used as the index of each group.
Specifically, 0, 1, 2, 3, . . . , 99 corresponding to the quotient, acquired by dividing 0, 3, 6, 9, . . . , 297 by 3, becomes the index with respect to the first group 310 as shown in FIG. 3.
Also, 0, 1, 2, 3, . . . , 99 corresponding to the quotient, acquired by dividing 1, 4, 7, 10, . . . , 298 by 3, becomes the index with respect to the second group 320 as shown in FIG. 3.
Also, 0, 1, 2, 3, . . . , 99 corresponding to the quotient, acquired by dividing 2, 5, 8, 11, . . . , 299 by 3, becomes the index with respect to the third group 330 as shown in FIG. 3.
As described above, since each of three groups is indicated by identical indexes, bit interleaving according to an exemplary embodiment of the present invention may be easily described.
FIG. 5 is a table illustrating a result of tone interleaving performed with respect to the result as shown in FIG. 4.
Referring to FIG. 5, tone interleaving is performed with respect to each of groups as shown in FIG. 4. Here, tone interleaving is performed by a method of selecting one data for every 10 input data.
Specifically, tone interleaving may be represented as,

T(j)=S{Floor(j/10)+10 Mod(j,10)}  [Equation 2]

However, in a 106.67 Mbps, 110 Mbps, and 200 Mbps MB-OFDM system, tone interleaving may be represented as,

T(j)=S{Floor(j/20)+10 Mod(j,20)}  [Equation 3]

FIG. 6 is a table illustrating a result of a cyclic shift performed with respect to the result as shown in FIG. 5.
Referring to FIG. 6, a shift operation has not been performed with respect to a first group 510 as shown in FIG. 5, but the shift operation has been performed with respect to a second group 520 and a third group 530 as shown in FIG. 5.
Specifically, a second group 620 of FIG. 6 corresponds to a result of placing index 33 to index 99 in front of index 0 to index 23 with respect to the second group 520 of FIG. 5.
Also, a third group 630 of FIG. 6 corresponds to a result of placing index 66 to index 99 in front of index 0 to index 56.
Accordingly, it is possible to effectively prevent data loss, which is caused by a burst error, by performing a cyclic shift as described above.
FIG. 7 is a table illustrating an output bit stream of a bit interleaver according to an exemplary embodiment of the present invention.
Referring to FIG. 7, it can be seen that the bit interleaver outputs a bit stream of 10 bits (from out0 to out9) every clock for 20 clocks.
In the case of a first group 710, since the bit stream is output by 10 bits for 20 clocks, 100 bit data of the first group 610, as shown in FIG. 6, is output twice. As described above, according to the present invention, it is possible to have a system characteristic, which is robust against an error, by outputting 100 bit data twice. Also, 100 bit data of the first group 610 is sequentially output from an eleventh clock 10. Also, as shown in FIG. 7, a data order is changed and output for 10 clocks from the first clock 0 to the tenth clock 9.
Accordingly, the bit interleaver may easily perform QPSK mapping and IFFT by outputting a bit stream as described above.
Also, in the case of a second group 720, since the bit stream is output by 10 bits for 20 clocks, 100 bit data of the second group 620, as shown in FIG. 6, is output twice. As described above, according to the present invention, it is possible to have a system characteristic, which is robust against an error, by outputting 100 bit data twice. Also, 100 bit data of the second group 620 is sequentially output from an eleventh clock 10. Also, as shown in FIG. 7, a data order is changed and output for 10 clocks from a first clock 0 to a tenth clock 9.
Also, in the case of a third group 730, since the bit stream is output by 10 bits for 20 clocks, 100 bit data of the third group 630, as shown in FIG. 6, is output twice. As described above, according to the present invention, it is possible to have a system characteristic, which is robust against an error, by repeatedly outputting 100 bit data twice. Also, 100 bit data of the third group 630 is sequentially output from an eleventh clock 10. Also, as shown in FIG. 7, a data order is changed and output for 10 clocks from the first clock 0 to the tenth clock 9.
FIG. 8 is a table illustrating a bit stream output from a memory to generate the output bit stream as shown in FIG. 7.
Referring to FIG. 8, the bit interleaver according to the present invention generates the output bit stream, as shown in FIG. 7, by using a bit stream of 10 bits (from out0 to out9) which is output every clock for 20 clocks.
In the case of a first group 810, 100 bit data of the first group 610 as shown in FIG. 6 is sequentially output from the eleventh clock 10. As shown in FIG. 8, a data order is changed and output for 10 clocks from the first clock 0 to the tenth clock 9.
FIG. 9 is a table illustrating a memory control signal applied to output the first group 810 as shown in FIG. 8 from a memory.
Referring to FIG. 9, an even bank number address Even_Rd_Addr, an odd bank number address Odd_Rd_Addr, and a bit order bit_order are applied to the memory every clock, clock 0 to clock 19, as shown in FIG. 8.
As an example, referring to FIG. 8, 0, 10, 20, 30, 40, 50, 60, 70, 80, and 90 are output for the eleventh clock 10. In this case, 0 is applied to the even bank number address Even_Rd_Addr of the memory, 2 is applied to the odd bank number address Odd_Rd_Addr, and 0 is applied to the bit order bit_order.
Referring to FIG. 2, when an address addr of a bank having an even bank number of 0, and a bit order bit_order of 0, 0, 60, 120, 180, and 240 is output. Here, when indicating as the quotient that is acquired by dividing 0, 60, 120, 180, and 240 by 3, and 0, 20, 40, 60, and 80 is output. Also, when the address addr of the bank having an odd bank number of 2, and the bit order bit_order of 2, 30, 90, 150, 210, and 270 is output. Here, when indicating as the quotient that is acquired by dividing 30, 90, 150, 210, and 270 by 3, and 10, 30, 50, 70, and 90 is output.
Accordingly, when applying a control signal to the memory and appropriately selecting a bank as shown in FIG. 9, the output bit stream corresponding to the first group 810 may be acquired as shown in FIG. 8.
FIG. 10 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to the first group 710 as shown in FIG. 7.
Referring to FIG. 10, only an order of a bit stream to be output from the memory is required to be appropriately changed to generate the output bit stream with respect to the first group 710.
Accordingly, the bit interleaver as shown in FIG. 10 appropriately changes the order of the bit stream to be output from the memory by using 10 multiplexers. In FIG. 10, 10 multiplexers select an input signal corresponding to ‘0’ for 10 clocks from the first clock 0 to the tenth clock 9, and select an input signal corresponding to ‘1’ for another 10 clocks from the eleventh clock 10 to the twentieth clock 19.
Referring again to FIG. 8, in the case of the second group 820, an output bit stream may not be generated with only a bit stream output from the memory for a single clock. The output bit stream may be generated by appropriately combining the bit stream output from memory for two clocks.
As an example, with respect to the second group 820, data output from the memory for two clocks 0 and 1 must be combined like an identification numeral 821, or data output from the memory for two clocks 10 and 11 must be combined like an identification numeral 822.
Also, a portion of bits of the bit stream, which is most initially output from the memory, i.e. 3, 13, and 23, must be stored until the last clock 19, to generate an output bit stream of the last clock 19 as shown in FIG. 7.
FIG. 11 is a table illustrating a memory control signal applied to output the second group 820, as shown in FIG. 8, from a memory.
Referring to FIG. 11, an even bank number address Even_Rd_Addr, an odd bank number address Odd_Rd_Addr, and a bit order bit_order are applied to the memory every clock, clock 0 to clock 19, as shown in FIG. 8.
As an example, referring to FIG. 8, 3, 13, 23, 33, 43, 53, 63, 73, 83, and 93 is output the eleventh clock 10. In this case, 3 is applied to the even bank number address Even_Rd_Addr of the memory, 0 is applied to the odd bank number address Odd_Rd_Addr, and 4 is applied to the bit order bit_order.
Referring to FIG. 2, when an address addr of a bank having an even bank number is 3, and a bit order bit_order is 4, 40, 100, 160, 220, and 280 is output. Here, when indicting as the quotient that is acquired by dividing 40, 100, 160, 220, and 280 by 3, and 13, 33, 53, 73, and 93 is output. Also, when the address addr of the bank having an odd bank number is 0, and the bit order bit_order is 4, 10, 70, 130, 190, and 250 is output. Here, when indicating as the quotient that is acquired by 10, 70, 130, 190, and 250 by 3, and 3, 23, 43, 63, and 83 is output.
Accordingly, when applying a control signal to the memory and appropriately selecting a bank as shown in FIG. 11, the output bit stream corresponding to the second group 820 may be acquired as shown in FIG. 8.
FIG. 12 is a block diagram illustrating a bit interleaver for generating an output bit stream with respect to the second group 720, as shown in FIG. 7.
Referring to FIG. 12, the bit interleaver, according to an exemplary embodiment of the present invention, includes delay devices 1210, a first MUX unit 1220, a second MUX unit 1230, a third MUX unit 1250, and a register 1240.
As described with FIGS. 3 through 6, the delay devices 1210 are applied with symbol interleaving and tone interleaving, delay a bit stream output from a memory, and generate a delayed bit stream.
Here, the memory outputs a bit stream corresponding to an index having an identical number in a one's column. As an example, the memory may output the bit stream corresponding to 0, 10, 20, 30, 40, 50, 60, 70, 80, and 90 having 0 in the one's column.
The first MUX unit 1220 selects any one of a bit of the bit stream output from the memory and a bit of the delayed bit stream, and generates a selection bit stream.
In this case, when selecting a bit corresponding to the bit stream output from the memory with respect to bits corresponding to bits stored in the register 1240 among the bit stream output from the memory, the first MUX unit 1220 selects a bit corresponding to the delayed bit stream with respect to bits not corresponding to the bits stored in the register 1240.
Specifically, as shown in FIG. 12, when multiplexers corresponding to a, b, and c output an input signal corresponding to ‘1’, multiplexers corresponding to d, e, f, g, h, i, and j output an input signal corresponding to ‘0’. Also, when the multiplexers corresponding to a, b, and c output an input signal corresponding to ‘0’, the multiplexers corresponding to d, e, f, g, h, i, and j output an input signal corresponding to ‘1’.
The second MUX unit 1230 generates an output bit stream by changing an order of the selection bit stream.
In an example shown in FIG. 12, the first MUX unit 1220 and the second MUX unit 1230 include 10 multiplexers.
In this case, the first MUX unit 1220 and the second MUX unit 1230 select an input signal corresponding to ‘0’ for 10 clocks from the first clock 0 to the tenth clock 9, and select an input signal corresponding to ‘1’ for another 10 clocks from the eleventh clock 10 to the twentieth clock 19.
The register 1240 stores a portion of the bits of a previous bit stream output from the memory, a nineteenth clock before the bit stream is output from the memory.
Specifically, the register 1240 stores a bit stream output from the memory in the first clock 0, and maintains the stored bit stream until the twentieth clock 19, and appropriately combines the stored bit stream with a bit stream output from the memory for the twentieth clock 19, to generate the output bit stream.
Also, the register 1240 performs writing for the first clock 0, and performs reading for the last clock 19.
The third MUX unit 1250 selects any one of the outputs of the register 1240 and a portion of the output bits of the second MUX unit 1230, and generates the output bit stream.
The third MUX unit 1250 generates three higher bits, for example, 7, 8, and 9, of the output bit stream by using three lower bits, for example, 0, 1, and 2, of the previous bit stream.
The third MUX unit 1250 selects an input signal corresponding to ‘1’ for only the last clock 19, and selects an input signal corresponding to ‘0’ for remaining clocks.
Referring again to FIG. 8, in the case of the third group 830, an output bit stream may not be generated with only a bit stream output from the memory for a single clock. The output bit stream may be generated by appropriately combining the bit stream output from memory for two clocks.
As an example, with respect to the third group 830, data output from the memory for two clocks 0 and 1 must be combined like an identification numeral 831, or data output from the memory for two clocks 10 and 11 must be combined like an identification numeral 832.
Also, a portion of the bits of the bit stream, which is initially output from the memory, i.e. 6, 16, 26, 36, 46, and 56, must be stored until the last clock 19, to generate an output bit stream of the last clock 19 as shown in FIG. 7.
FIG. 13 is a table illustrating a memory control signal applied to output the third group 830 as shown in FIG. 8, from a memory.
Referring to FIG. 13, an even bank number address Even_Rd_Addr, an odd bank number address Odd_Rd_Addr, and a bit order bit_order are applied to the memory every clock, from clock 0 to clock 19, as shown in FIG. 8.
As an example, referring to FIG. 8, the 6, 16, 26, 36, 46, 56, 66, 76, 86, and 96 is output for the eleventh clock 10. In this case, 4 is applied to the even bank number address Even_Rd_Addr of the memory, 1 is applied to the odd bank number address Odd_Rd_Addr, and 2 is applied to the bit order bit_order.
Referring to FIG. 2, when an address addr of a bank having an even bank number of 4, and a bit order bit_order of 2, 50, 110, 170, 230, and 290 is output. Here, when indicating as the quotient that is acquired by dividing 50, 110, 170, 230, and 290 by 3, and 16, 36, 56, 76, and 96 is output. Also, when the address addr of the bank having an odd bank number of 1, and the bit order bit_order of 2, 20, 80, 140, 200, and 260 is output. Here, when indicating as the quotient that is acquired by dividing 20, 80, 140, 200, and 260 by 3, and 6, 26, 46, 66, and 86 is output.
Accordingly, when applying a control signal to the memory and appropriately selecting a bank as shown in FIG. 13, the output bit stream corresponding to the third group 830 may be acquired as shown in FIG. 8.
FIG. 14 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to the third group 730 as shown in FIG. 7.
Referring to FIG. 14, the bit interleaver according to an exemplary embodiment of the present invention includes delay devices 1410, a first MUX unit 1420, a second MUX unit 1430, a third MUX unit 1450, and a register 1440.
As described with FIGS. 3 through 6, the delay devices 1410 are applied with symbol interleaving and tone interleaving, delay a bit stream output from a memory, and generate a delayed bit stream.
Here, the memory outputs a bit stream corresponding to an index having an identical number in a one's column. As an example, the memory may output the bit stream corresponding to 0, 10, 20, 30, 40, 50, 60, 70, 80, and 90 having 0 in the one's column.
The first MUX unit 1420 selects any one of a bit of the bit stream output from the memory and a bit of the delayed bit stream, and generates a selection bit stream.
In this case, when selecting a bit corresponding to the bit stream output from the memory with respect to bits corresponding to the bits stored in the register 1440 among the bit stream output from the memory, the first MUX unit 1420 selects a bit corresponding to the delayed bit stream with respect to bits not corresponding to the bits stored in the register 1440.
Specifically, as shown in FIG. 14, when multiplexers corresponding to a, b, c, d, e, and f output an input signal corresponding to ‘1’, multiplexers corresponding to g, h, i, and j output an input signal corresponding to ‘0’. Also, when the multiplexers corresponding to a, b, c, d, e, and f output an input signal corresponding to ‘0’, the multiplexers corresponding to g, h, i, and j output an input signal corresponding to ‘1’.
The second MUX unit 1430 generates an output bit stream by changing the order of the selection bit stream.
In an example shown in FIG. 14, each of the first MUX unit 1420 and the second MUX unit 1430 include 10 multiplexers.
In this case, the first MUX unit 1420 and the second MUX unit 1430 select an input signal corresponding to ‘0’ for 10 clocks from the first clock 0 to the tenth clock 9, and select an input signal corresponding to ‘1’ for another 10 clocks from the eleventh clock 10 to the twentieth clock 19.
The register 1440 stores a portion of bits of a previous bit stream output from the memory, a nineteenth clock before the bit stream is output from the memory.
Specifically, the register 1440 stores a bit stream output from the memory in the first clock 0, and maintains the stored bit stream until the twentieth clock 19, and appropriately combines the stored bit stream with a bit stream output from the memory in the twentieth clock 19, to generate the output bit stream. Also, the register 1440 performs writing for the first clock 0, and performs reading for the last clock 19.
The third MUX unit 1450 selects any one of an output of the register 1440 and a portion of output bits of the second MUX unit 1430, and generates the output bit stream.
The third MUX unit 1450 generates six higher bits, for example, 4, 5, 6, 7, 8, and 9, of the output bit stream by using six lower bits, for example, 0, 1, 2, 3, 4, and 5, of the previous bit stream.
The third MUX unit 1450 selects an input signal corresponding to ‘1’ for only the last clock 19, and selects an input signal corresponding to ‘0’ for remaining clocks.
FIG. 15 is a table illustrating an example of a 600 bit input stored in a memory when an interleaver operates in 106.7 Mbps or 200 Mbps.
Referring to FIG. 15, the memory includes 10 banks 1510, 1511, 1512, 1513, 1514, 1515, 1516, 1517, 1518, and 1519. Here, a bank number may be represented as j×2+i where i designates an integer, either 0 and 1, and j designates an integer from 0 to 4. Specifically, the bank number is determined by i and j. As an example, when both i and j are 0, the bank number becomes 0. Also, when i is 1 and j is 2, the bank number becomes 5, and when i is 1 and j is 4, the bank number becomes 9.
Numbers as shown in FIG. 15 designate an order of input data. Specifically, number 0 to number 599 as shown in FIG. 15 designates first input data to 600th input data.
FIG. 16 is a table illustrating a result of symbol interleaving performed with respect to the 600 bit input as shown in FIG. 15.
Referring to FIG. 16, when performing symbol interleaving with respect to the 600 bit input as shown in FIG. 15, the 600 bit input data is classified into three groups. A first group 1610 corresponds to a group of input data having a remainder of 0 when dividing an order of input data by 3. A second group 1620 corresponds to a group of input data having a remainder of 1 when dividing an order of input data by 3, and a third group 1630 corresponds to a group of input data having a remainder of 2 when dividing an order of input data by 3.
As described above, symbol interleaving may be represented as equation 1.
FIG. 17 is a table illustrating a result of indicating the result of symbol interleaving as shown in FIG. 16 as index 0 to index 199.
Referring to FIG. 17, each of the first group 1610, the second group 1620, and the third group 1630 as shown in FIG. 16 is indicated as index 0 to index 199.
Here, the quotient, acquired by dividing an order by 3, is used as the index of each group.
Specifically, 0, 1, 2, 3, . . . , 199 corresponding to the quotient, acquired by dividing 0, 3, 6, 9, . . . , 597 by 3, becomes the index with respect to the first group 1610 as shown in FIG. 16.
Also, 0, 1, 2, 3, . . . , 199 corresponding to the quotient, acquired by dividing 1, 4, 7, 10, . . . , 598 by 3, becomes the index with respect to the second group 1620 as shown in FIG. 16.
Also, 0, 1, 2, 3, . . . , 199 corresponding to the quotient, acquired by dividing 2, 5, 8, 11, . . . , 599 by 3, becomes the index with respect to the third group 1630 as shown in FIG. 16.
As described above, since each of three groups is indicated by identical indexes, bit interleaving according to an exemplary embodiment of the present invention may be easily described.
FIG. 18 is a table illustrating a result of tone interleaving performed with respect to the result as shown in FIG. 17.
Referring to FIG. 18, tone interleaving is performed with respect to each of groups as shown in FIG. 17. Here, tone interleaving is performed by a method of selecting one data for every 10 input data.
As described above, tone interleaving may be represented as equation 3.
FIG. 19 is a table illustrating a result of a cyclic shift performed with respect to the result as shown in FIG. 18.
Referring to FIG. 19, a shift operation has not been performed with respect to a first group 1810 as shown in FIG. 18, but the shift operation has been performed with respect to a second group 1820 and a third group 1830 as shown in FIG. 18.
Specifically, a second group 1920 of FIG. 19 corresponds to a result of placing index 63 to index 199 in front of index 0 to index 53 with respect to the second group 1820 of FIG. 18.
Also, a third group 1930 of FIG. 19 corresponds to a result of placing index 126 to index 199 in front of index 0 to index 116.
Accordingly, it is possible to effectively prevent data loss, which is caused by a burst error, by performing a cyclic shift as described above.
FIG. 20 is a table illustrating an output bit stream of a bit interleaver according to an exemplary embodiment of the present invention.
Referring to FIG. 20, it can be seen that the bit interleaver outputs a bit stream of 10 bits every clock for 20 clocks.
In the case of a first group 2010, since the bit stream is output by 10 bits for 20 clocks, 200 bit data of the first group 1910, as shown in FIG. 19, is output twice. An output order of the output bit stream is shown in FIG. 20.
Also, in the case of a second group 2020, since the bit stream is output by 10 bits for 20 clocks, 200 bit data of the second group 1920, as shown in FIG. 19, is output twice. An output order of the output bit stream is shown in FIG. 20.
Also, in the case of a third group 2030, since the bit stream is output by 10 bits for 20 clocks, 200 bit data of the third group 1930, as shown in FIG. 19, is output twice. An output order of the output bit stream is shown in FIG. 20.
FIG. 21 is a table illustrating a bit stream output from a memory to generate the output bit stream as shown in FIG. 20.
Referring to FIG. 21, the bit interleaver according to the present invention generates the output bit stream as shown in FIG. 20 by using a bit stream (of 10 bits from out0 to out9) which is output every clock for 20 clocks.
In the case of a first group 2110, 100 bit data of the first group 1910 as shown in FIG. 19 is sequentially output from the eleventh clock 10. Data is output in an order, as shown in FIG. 21, for 10 clocks from the first clock 0 to the tenth clock 9.
FIG. 22 is a table illustrating a memory control signal applied to output the first group 2110 as shown in FIG. 21 from a memory.
Referring to FIG. 22, an even bank number address Even_Rd_Addr, an odd bank number address Odd_Rd_Addr, and a bit order bit_order are applied to the memory every clock, clock 0 to clock 19, as shown in FIG. 21.
As an example, referring to FIG. 21, 0, 10, 20, 30, 40, 50, 60, 70, 80, and 90 is output for the eleventh clock 10. In this case, 0 is applied to the even bank number address Even_Rd_Addr of the memory, 2 is applied to the odd bank number address Odd_Rd_Addr, and 0 is applied to the bit order bit_order.
Referring to FIG. 15, when an address addr of a bank having an even bank number of 0, and a bit order bit_order of 0, 0, 60, 120, 180, and 240 is output. Here, when indicating as the quotient that is acquired by dividing 0, 60, 120, 180, and 240 by 3, and 0, 20, 40, 60, and 80 is output. Also, when the address addr of the bank having an odd bank number of 2, and the bit order bit_order of 2, 30, 90, 150, 210, and 270 is output. Here, when representing the quotient that is acquired by dividing 30, 90, 150, 210, and 270 by 3, and 10, 30, 50, 70, and 90 is output.
Accordingly, when applying a control signal to the memory and appropriately selecting a bank as shown in FIG. 22, the output bit stream corresponding to the first group 2110 may be acquired as shown in FIG. 21.
Specifically, in the bit interleaver for generating an output bit stream with respect to the first group 2010 of FIG. 20, a bit stream output from the memory becomes the output bit stream as is.
Referring again to FIG. 21, in the case of the second group 2120, an output bit stream may not be generated with only a bit stream output from the memory for a single clock. The output bit stream may be generated by appropriately combining the bit stream output from memory for two clocks.
As an example, with respect to the second group 2120, data output from the memory for two clocks 0 and 1 must be combined like an identification numeral 2121.
Also, a portion of bits of the bit stream, which is most initially output from the memory, i.e. 8, 18, 28, 38, 48, and 58, must be stored until the last clock 19, to generate an output bit stream of the last clock 19 as shown in FIG. 20.
FIG. 23 is a table illustrating a memory control signal applied to output the second group 2120 as shown in FIG. 21 from a memory.
Referring to FIG. 23, an even bank number address Even_Rd_Addr, an odd bank number address Odd_Rd_Addr, and a bit order bit_order are applied to the memory every clock, clock 0 to clock 19, as shown in FIG. 21.
As an example, referring to FIG. 21, a 3, 13, 23, 33, 43, 53, 63, 73, 83, and 93 is output for the eleventh clock 10. In this case, 3 is applied to the even bank number address Even_Rd_Addr of the memory, 0 is applied to the odd bank number address Odd_Rd_Addr, and 4 is applied to the bit order bit_order.
Referring to FIG. 15, when an address addr of a bank having an even bank number of 3, and a bit order bit order of 4, 40, 100, 160, 220, and 280 is output. Here, when indicating as the quotient that is acquired by dividing 40, 100, 160, 220, and 280 by 3, and 13, 33, 53, 73, and 93 is output. Also, when the address addr of the bank having an odd bank number of 0, and the bit order bit_order of 4, 10, 70, 130, 190, and 250 is output. Here, when indicating as the quotient that is acquired by dividing 10, 70, 130, 190, and 250 by 3, and 3, 23, 43, 63, and 83 is output.
Accordingly, when applying a control signal to the memory and appropriately selecting a bank as shown in FIG. 23, the output bit stream corresponding to the second group 2120 may be acquired as shown in FIG. 21.
FIG. 24 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to the second group 2020 as shown in FIG. 20.
Referring to FIG. 24, the bit interleaver according to an exemplary embodiment of the present invention includes delay devices 2410, a register 2420, and a MUX unit 2430.
As described with FIGS. 16 through 19, the delay devices 2410 are applied with symbol interleaving and tone interleaving and delays a portion, for example, 6, 7, 8, and 9, of bits of a bit stream output from a memory, and generate a delayed bit stream.
Here, the memory outputs a bit stream corresponding to an index having an identical number in a one's column. As an example, the memory may output the bit stream corresponding to 0, 10, 20, 30, 40, 50, 60, 70, 80, and 90 having 0 in the one's column.
The register 2420 stores a portion of bits of a previous bit stream output from the memory, a nineteenth clock before the bit stream is output from the memory.
Specifically, the register 2420 stores a bit stream output from the memory in the first clock 0, and maintains the stored bit stream until the twentieth clock 19, and appropriately combines the stored bit stream with a bit stream output from the memory for the twentieth clock 19, to generate the output bit stream.
Also, the register 2420 performs writing for the first clock 0, and performs reading for the last clock 19.
The MUX unit 2430 selects any one of an output of the register 2420 and bits, for example, 0, 1, 2, 3, 4, and 5, corresponding to a bit stream. Here, the bit stream is not delayed by the delay devices and output from the memory.
The bit interleaver as shown in FIG. 24 generates an output bit stream by using an output of the delay devices 2410 and the MUX unit 2430.
In this case, the memory may output a bit stream of 10 bits, and an addition of a number of bits corresponding to the delay devices 2410 and a number of bits corresponding to the register 2420 may be 10.
The MUX unit 2430 includes six multiplexers.
Here, the MUX unit 2430 selects an input signal corresponding to ‘0’ for nineteen clocks from a first clock 0 to a nineteenth clock 18, and selects an input signal corresponding to ‘1’ for a twentieth clock 19.
The MUX unit 2430 generates six higher bits, for example, 4, 5, 6, 7, 8, and 9, of the output bit stream by using six lower bits, for example, 0, 1, 2, 3, 4, and 5, of the previous bit stream.
Referring again to FIG. 21, in the case of the third group 2130, an output bit stream may not be generated with only a bit stream output from the memory for a single clock. The output bit stream may be generated by appropriately combining the bit stream output from memory for two clocks.
As an example, with respect to the third group 2130, data output from the memory for two clocks 0 and 1 must be combined like an identification numeral 2131.
Also, a portion of the bits of the bit stream, which is initially output from the memory, i.e. 101 and 111, must be stored until the last clock 19, to generate an output bit stream of the last clock 19 as shown in FIG. 20.
FIG. 25 is a table illustrating a memory control signal applied to output the third group 2130 as shown in FIG. 21 from a memory.
Referring to FIG. 25, an even bank number address Even_Rd_Addr, an odd bank number address Odd_Rd_Addr, and a bit order bit_order are applied to the memory every clock, clock 0 to clock 19, as shown in FIG. 21.
As an example, referring to FIG. 21, 106, 116, 126, 136, 146, 156, 166, 176, 186, a 196 is output for the eleventh clock 10. In this case, 9 is applied to the even bank number address Even_Rd_Addr of the memory, 6 is applied to the odd bank number address Odd_Rd_Addr, and 2 is applied to the bit order bit_order.
Referring to FIG. 15, when an address addr of a bank having an even bank number of 9, and a bit order bit_order of 2, 350, 410, 470, 530, and 590 is output. Here, when indicating the quotient that is acquired by dividing 350, 410, 470, 530, and 590 by 3, and 116, 136, 156, 176, and 196 is output. Also, when the address addr of the bank having an odd bank number of 6, and the bit order bit_order of 2, 320, 380, 440, 500, and 560 is output. Here, when indicating the quotient that is acquired by dividing 320, 380, 440, 500, and 560 by 3, and 106, 126, 146, 166, and 186 is output.
Accordingly, when applying a control signal to the memory and appropriately selecting a bank as shown in FIG. 25, the output bit stream corresponding to the third group 2130 may be acquired, as shown in FIG. 21.
FIG. 26 is a block diagram illustrating a bit interleaver to generate an output bit stream with respect to the third group 2030, as shown in FIG. 20.
Referring to FIG. 26, the bit interleaver according to an exemplary embodiment of the present invention includes delay devices 2610, a register 2620, and a MUX unit 2630.
As described with FIGS. 16 through 19, the delay devices 2610 are applied with symbol interleaving and tone interleaving and delays a portion, for example, 2, 3, 4, 5, 6, 7, 8, and 9, of bits of a bit stream output from a memory, and generate a delayed bit stream.
Here, the memory outputs a bit stream corresponding to an index having an identical number in a one's column. As an example, the memory may output the bit stream corresponding to 0, 10, 20, 30, 40, 50, 60, 70, 80, and 90 having 0 in the one's column.
The register 2620 stores a portion of bits of a previous bit stream output from the memory, a nineteenth clock before the bit stream is output from the memory.
Specifically, the register 2620 stores a bit stream output from the memory in the first clock 0, and maintains the stored bit stream until the twentieth clock 19, and appropriately combines the stored bit stream with a bit stream output from the memory for the twentieth clock 19, to generate the output bit stream.
Also, the register 2620 performs writing for the first clock 0, and performs reading for the last clock.
The MUX unit 2630 selects any one of an output of the register 2620 and bits, for example, 0 and 1, corresponding to a bit stream. Here, the bit stream is not delayed by the delay devices and output from the memory
The bit interleaver as shown in FIG. 26 generates an output bit stream by using an output of the delay devices 2610 and the MUX unit 2630.
In this case, the memory may output a bit stream of 10 bits, and an addition of a number of bits corresponding to the delay devices 2610 and a number of bits corresponding to the register 2620 may be 10. Specifically, bits, which are not inputted into the delay devices 2610 from the bit stream output from the memory, are inputted into the register 2620.
The MUX unit 2630 includes two multiplexers.
Here, the MUX unit 2630 selects an input signal corresponding to ‘0’ for nineteen clocks from a first clock 0 to a nineteenth clock 18, and selects an input signal corresponding to ‘1’ for a twentieth clock 19.
The MUX unit 2630 generates two higher bits, for example, 8 and 9, of the output bit stream by using two lower bits, for example, 0 and 1, of the previous bit stream.
FIG. 27 is a flowchart illustrating a bit interleaving method according to an exemplary embodiment of the present invention.
Referring to FIG. 27, in operation S2710, the bit interleaving method according to the present exemplary embodiment outputs a bit stream corresponding to a result of symbol interleaving and tone interleaving, from a memory.
Also, in operation S2710, the bit interleaving method may output bits corresponding to indexes having an identical number in a one's column as the bit stream.
In operation S2720, the bit interleaving method selects any one of a bit of the bit stream output from the memory and a bit of a delayed bit stream, which is acquired by delaying the bit stream, and generates a selection bit stream.
In operation S2730, the bit interleaving method generates an output bit stream by changing an order of the selection bit stream.
In operation S2740, the bit interleaving method stores a portion of bits of a previous bit stream output from the memory, a predetermined clock before the bit stream is output from the memory, and replaces a portion of the bits of the output bit stream with the stored bits.
Also, in operation S2740, the bit interleaving method may generate a predetermined number of higher bits of the output bit stream by using a predetermined number of lower bits of the previous bit stream.
FIG. 28 is a flowchart illustrating a bit interleaving method according to another embodiment of the present invention.
Referring to FIG. 28, in operation S2810, the bit interleaving method according to the present exemplary embodiment outputs a bit stream corresponding to a result of symbol interleaving and tone interleaving, from a memory.
In operation S2820, the bit interleaving method generates a delaedy bit stream by delaying a portion of bits of the bit stream output from the memory.
In operation S2830, the bit interleaving method generates an output bit stream by storing a portion of bits of a previous bit stream output from the memory, a predetermined clock before the bit stream is output from the memory, and replaces a portion of the bits of the output bit stream with the stored bits.
Descriptions related to a bit interleaver may be applicable to the method as shown in FIGS. 27 and 28.
As described above, according to the present invention, it is possible to easily and effectively perform bit interleaving including a cyclic shift.
Also, according to the present invention, it is possible to effectively embody a bit interleaver which can satisfy requirements of at least WiMedia Ultra-Wideband physical layer specification (UWB PHY) spec 1.0.
Also, according to the present invention, it is possible to easily perform a cyclic shift operation by using an output feature of results of symbol interleaving and tone interleaving.
Although a few exemplary embodiments of the present invention have been shown and described, the present invention is not limited to the described exemplary embodiments. Instead, it would be appreciated by those skilled in the art that changes may be made to these exemplary embodiments without departing from the principles and spirit of the invention, the scope of which is defined by the claims and their equivalents.

## Claims

1. A bit interleaver comprising:
a plurality of delay devices which are provided with a bit stream output from a memory, the bit stream being symbol-interleaved and tone interleaved, and delay the bit stream output to generate a delayed bit stream;
a first MUX unit which selects one of a bit of the bit stream output from the memory and a bit of the delayed bit stream, to generate a selection bit stream; and
a second multiplexer (MUX) unit which changes an order of the selection bit stream to generate an output bit stream.

2. The bit interleaver of claim 1, further comprising:
a register which stores a portion of bits of a previous bit stream output from the memory, a clock before the bit stream is output from the memory; and
a third MUX unit which selects one of an output of the register and a portion of output bits of the second MUX unit to generate the output bit stream.

3. The bit interleaver of claim 2, wherein bits of the output bit stream correspond to indexes and first digits of the indexes are the same.

4. The bit interleaver of claim 3, wherein the memory outputs a bit stream of 10 bits, the delay devices correspond to 10 bits, and the first MUX unit comprises 10 multiplexers.

5. The bit interleaver of claim 4, wherein the first MUX unit selects bits of the delayed bit stream, when selecting either bits of the bit stream output from the memory or bits of the delayed bit stream with respect to bits corresponding to the bits stored in the register.

6. The bit interleaver of claim 5, wherein the bit interleaver outputs an output bit stream every clock for 20 clocks, and the first MUX unit and the second MUX unit operate based on a first control signal for 10 clocks from a first clock to a tenth clock, and operate based on a second control signal for another 10 clocks from an eleventh clock to a twentieth clock.

7. The bit interleaver of claim 6, wherein the clock corresponds to a nineteenth clock.

8. The bit interleaver of claim 7, wherein the third MUX unit generates a number of higher bits of the output bit stream by using a number of lower bits of the previous bit stream.

9. The bit interleaver of claim 8, wherein the number of bits is 3.

10. The bit interleaver of claim 8, wherein the number of bits is 8.

11. A bit interleaver comprising:
a plurality of delay devices which are provided with a bit stream output from a memory, the bit stream being symbol-interleaved and tone-interleaved, and delay a portion of bits of the bit stream output to generate a delayed bit stream;
a register which stores a portion of bits of a previous bit stream output from the memory, a clock before the bit stream is output from the memory, the previous bit stream being symbol-interleaved and the tone-interleaved; and
a multiplexer (MUX) unit which selects one of an output of the register and bits corresponding to a bit stream which is not delayed by the delay devices and output from the memory,
wherein the bit interleaver generates an output bit stream using the delay devices and an output of the MUX unit.

12. The bit interleaver of claim 11, wherein bits of the output bit stream correspond to indexes and first digits of the indexes are the same.

13. The bit interleaver of claim 12, wherein the bit steam output from the memory has 10 bits, and an addition of a number of bits corresponding to the delay devices and a number of bits corresponding to the register is 10.

14. The bit interleaver of claim 13, wherein the bit interleaver outputs an output bit stream for 20 clocks, and the MUX unit operates by a first control signal for 19 clocks from a first clock to a nineteenth clock, and operates by a second control signal for a twentieth clock.

15. The bit interleaver of claim 11, wherein the clock corresponds to a nineteenth clock.

16. The bit interleaver of claim 15, wherein the portion of the bits of the previous bit stream include bits not delayed in the delay devices among the bit stream output from the memory.

17. The bit interleaver of claim 16, wherein the MUX unit generates a number of higher bits of the output bit stream based on a same number of lower bits of the previous bit stream.

18. The bit interleaver of claim 17, wherein the same number of bits is 6.

19. The bit interleaver of claim 17, wherein the same number of bits is 2.

20. A bit interleaving method comprising:
outputting from a memory a bit stream, the bit steam being symbol-interleaved and tone-interleaved;
selecting one of a bit of the bit stream output from the memory and a bit of a delayed bit stream, which is acquired by delaying the bit stream, to generate a selection bit stream; and
generating an output bit stream by changing an order of the selection bit stream.

21. The bit interleaving method of claim 20, further comprising:
storing a portion of bits of a previous bit stream output from the memory, a clock before a bit stream is output from the memory, the previous bit stream being symbol-interleaved and tone-interleaved, and replacing a portion of bits of the output bit stream with the stored bits.

22. The bit interleaving method of claim 21, wherein the outputting outputs bits corresponding to indexes, having an identical number in first digits of the indexes, as the bit stream.

23. The bit interleaving method of claim 22, wherein the replacing generates a number of higher bits of the output bit stream based on a same number of lower bits of the previous bit stream.

24. A bit interleaving method comprising:
outputting from a memory a bit stream, the bit stream being symbol-interleaved and tone-interleaved;
generating a delayed bit stream by delaying a portion of bits of the bit stream output from the memory; and
generating an output bit stream by storing a portion of bits of a previous bit stream output from the memory, a clock before the bit stream is output from the memory, the previous bit stream being symbol interleaved and tone-interleaved, and replacing a portion of bits of the output bit stream with the stored bits.

25. The bit interleaving method of claim 24, wherein the outputting outputs bits corresponding to indexes as the bit stream, and first digits of the indexes are the same.

26. The bit interleaving method of claim 25, wherein the bit stream output from the memory has 10 bits, and an addition of a number of the delayed bits and a number of the stored bits is 10.

27. The bit interleaving method of claim 25, wherein the generating the output bit stream generates a number of higher bits of the output bit stream based on a same number of lower bits of the previous bit stream.