System, apparatus, and method for loading bits into sub-channels

Not applicable.

1. Field of the Invention

The present invention relates to a system, an apparatus, and a method for loading bits into sub-channels. More particularly, the present invention relates to a system, an apparatus, and a method for loading bits into sub-channels according to the different sub-channel qualities.

2. Descriptions of the Related Art

Currently, most digital communication systems, such as orthogonal frequency division multiplexing (OFDM) and asymmetric digital subscriber line (ADSL), employ multi-channel or multi-carrier transmission. It is quite important in the field of multi-channel transmission to be effectively allocating bits into sub-channels so that the performance is able to be increased and the bit error rate (BER) during the transmission is able to be reduced.

Power and data rate are involved in a bit loading method, which allocates bits and power to sub-channels. Conventionally, the bit loading methods are either subject to a fixed power or a fixed data rate. When a bit loading method is subject to a fixed power, the method intends to maximize the data rate under the fixed power. When a bit loading method is subject to a fixed data rate, the method intends to minimize the power.

In U.S. Pat. No. 6,418,161, a bit loading method subject to a fixed power is provided, wherein the power is limited by a power spectral-density mask and an aggregate signal power constraint. The method allocates bits to sub-channels according to the lowest marginal power-cost per bit. If there is remaining aggregate signal power after all the bits have been allocated to the sub-channels with sufficient margins to carry a bit, additional bits are assigned to the sub-channels using frequency-domain-spreading across several sub-channels at the corresponding reduced power levels. Although optimal, this method is too complicated for initial bit allocation.

On the contrary, the bit-filling method and the bit-removal method are subject to a fixed data rate. Both of them allocate or remove bits iteratively based on the power cost of sub-channels. The bit-filling method initially allocates zero bits to all sub-channels and then adds one bit at a time to the sub-channel that requires minimum additional power until the target data rate is achieved. The bit-removal method initially allocates maximal bits to the sub-channels and then removes one bit at a time from the sub-channel that reduces the maximum power until the target data rate is achieved. Both the bit-filling and bit-removal methods result in the same bit allocation. Although both methods can achieve optimal results, they are complicated and inefficient due to the bit-based iteration.

Although optimal bit loading methods have been proposed in this field, all of them are extremely complicated. Thus, an efficient approach for allocating bits to sub-channels is still needed in this field.

An objective of the present invention is to provide a system. The system comprises a processing unit and an interface. The processing unit is configured to load a predetermined number of bits into a plurality of sub-channels. The processing unit comprises a sort module, a calculation module, and a decision module. The sort module is configured to sort the sub-channels into a plurality of sorted sub-channels according to a quality value of each of the sub-channels. The calculation module is configured to calculate a difference value for each of the sorted sub-channels, except for the first sorted sub-channel, according to the corresponding quality value. The decision module is configured to decide a number of bits for each of the sorted sub-channels according to the difference values, wherein a summation of the numbers is equal to the predetermined number. The interface is configured to transmit the predetermined number of bits.

Another objective of the present invention is to provide an apparatus for loading a predetermined number of bits into a plurality of sub-channels. The apparatus comprises a sort module, a calculation module, and a decision module. The sort module is configured to sort the sub-channels into a plurality of sorted sub-channels according to a quality value of each of the sub-channels. The calculation module is configured to calculate a difference value for each of the sorted sub-channels, except for the first sorted sub-channel, according to the corresponding quality values. The decision module is configured to decide a number of bits for each of the sorted sub-channels according to the difference values, wherein a summation of the numbers is equal to the predetermined number.

A further objective of the present invention is to provide an apparatus for loading a predetermined number of bits into a plurality of sub-channels. The apparatus comprises (1) means for sorting the sub-channels into a plurality of sorted sub-channels according to a quality value of each of the sub-channels, (2) means for calculating a difference value for each of the sorted sub-channels, except for the first sorted sub-channel, according to the corresponding quality values, and (3) means for deciding a number of bits for each of the sorted sub-channels according to the difference values, wherein a summation of the numbers is equal to the predetermined number.

Yet a further objective of the present invention is to provide a method for loading a predetermined number of bits to a plurality of sub-channels. The method comprises the following steps: (1) sorting the sub-channels into a plurality of sorted sub-channels according to a quality value of each of the sub-channels, (2) calculating a difference value for each of the sorted sub-channels, except for the first sorted sub-channel, according to the corresponding quality values, and (3) deciding a number of bits for each of the sorted sub-channels according to the difference values, wherein a summation of the numbers is equal to the predetermined number.

According to the aforementioned arrangements and steps, the present invention is able to exploit the differences of the channel qualities between sub-channels and then load bits into the sub-channels based on the differences. Using these differences, more than one bit can be loaded per iteration. Consequently, the present invention can load bits into sub-channels more efficiently.

The detailed technology and preferred embodiments implemented for the subject invention are described in the following paragraphs accompanying the appended drawings for people skilled in this field to well appreciate the features of the claimed invention.

FIG. 1 illustrates a first embodiment of the present invention;

FIG. 2A illustrates the difference values of the sorted sub-channels of the first embodiments;

FIG. 2B illustrates an example of the temporary number and the number of bits of each of the sorted sub-channels;

FIG. 2C illustrates another example of the temporary number and the number of bits of each of the sorted sub-channels;

FIG. 3A illustrates the second embodiment of the present invention; and

FIG. 3B illustrates the second embodiment of the present invention.

FIG. 1 illustrates a first embodiment of the present invention, which is a communication transmission system 1 . The communication transmission system 1 comprises a processing unit 11 and an interface 15 . The processing unit 11 comprises a sort module 12 , a calculation module 13 , and a decision module 14 . The decision module 14 comprises a selection module 141 , a comparison module 142 , and a process module 143 . The selection module 141 comprises a group module 141 a and a decrease module 141 b . The process module 143 comprises a load module 143 a and an increase module 143 b . Each of the modules can be realized by an apparatus that has processing or operating ability, such as a CPU.

In the first embodiment, the communication transmission system 1 comprises N sub-channels with a required data rate B req . The communication transmission system 1 will assign b i bits to the i th sub-channel so that

∑ i = 1 N ⁢ b i = B req ⁢ ⁢ and ⁢ ⁢ ∑ i = 1 N ⁢ P i

is minimized, wherein b i ε{0, 1, . . . , b }, ∀1≦i≦N, b is the maximum of the number of bits that can be assigned to each of the N sub-channels, and P i is the consumed power of the i th sub-channel. Generally speaking, the first embodiment comprises two stages. The first stage is the loading stage, while the second stage is the removing stage.

First, the loading stage is performed. The processing unit 11 is configured to load a predetermined number of bits, i.e. B req bits, into the N sub-channels to achieve the required data rate B req . The sort module 12 sorts the N sub-channels into N sorted sub-channels according to a channel gain to noise ratio (CNR) of each of the sub-channels. It is noted that the CNRs can be replaced by other values that represent the qualities of the sub-channels in other embodiments. After sorting, the relations of the CNRs can be represented as CNR 1 ≧ . . . ≧CNR N , wherein the subscripts indicate the order of the sorted sub-channels. That is, CNR 1 indicates the CNR of the first sorted sub-channel.

Then, the calculation module 13 calculates a difference value d i for each of the sorted sub-channels, except for the first sorted sub-channel, according to the corresponding CNR i . To be more specific,

d i = ⌊ log 2 ⁡ ( C ⁢ ⁢ N ⁢ ⁢ R 1 C ⁢ ⁢ N ⁢ ⁢ R i ) ⌋ ,

wherein i denotes the index of the i th sorted sub-channel and d i denotes the difference value between the i th sorted sub-channel and the first sorted sub-channel. In this embodiment, the difference values d i indicate the difference value of the number of bits assigned to the first sorted sub-channel and the number of bits assigned to the i th sorted sub-channel.

To be more concrete, it is assumed that the parameters are set to N=29, B req =58, and b =6. Based on the corresponding CNRs, d 2 =1, d 3 =1, d 4 =2, d 5 =2, d 6 =2, d 7 =4, d 8 =4, d 9 =4, d 10 =4, d 11 =6, d 12 =6, d 13 =6, d 14 =6, d 15 =11, d 16 =12, d 17 =12, d 18 =12, d 19 =12, d 20 =12, d 21 =12, d 22 =12, d 23 =13, d 24 =13, d 25 =13, d 26 =13, d 27 =13, d 28 =13, and d 29 =13 are derived. FIG. 2A visualizes the difference values by setting the number of bits assigned to the sub-channel with the lowest CNR as one. In FIG. 2A , the horizontal axis represents the index of the sorted sub-channels, while the vertical axis represents the number of bits. From FIG. 2A , if the sub-channel with the lowest CNR, i.e. the 29 th sorted sub-channel, has one bit, then the first sorted sub-channel has 14 (13+1) bits because d 29 =13. FIG. 2A is used to demonstrate the difference values but not the loading result of the first embodiment.

The decision module 14 then utilizes several modules to decide a number of bits b i for each of the sorted sub-channels according to the difference value d i , wherein a summation of the numbers is equal to the predetermined number. The details of the process to determine the number of bits, b i , are explained in the following paragraphs.

The decision module 14 decides a temporary number t 1 of “1” for the first sorted sub-channel. In other embodiments, the temporary number t 1 may be set to other values depending on the particular situation. Then, the calculation module 13 calculates a calculated number c i for each of the rest sorted sub-channels by subtracting the corresponding difference value from the number of bits of the first sorted sub-channel, that is, calculating c i =t 1 −d i . The calculated values c i are derived as follows: c 2 =0, c 3 =0, c 4 =−1, c 5 =−1, c 6 =−1, c 7 =−3, c 8 =−3, c 9 =−3, c 10 =−3, c 11 =−5, c 12 =−5, c 13 =−5, c 14 =−5, c 15 =−10, c 16 =−11, c 17 =−11, c 18 =−11, c 19 =−11, c 20 =−11, c 21 =−11, c 22 =−11, c 23 =−12, c 24 =−12, c 25 =−12, c 26 =−12, c 27 =−12, c 28 =−12, and c 29 =−12.

Then, the selection module 141 selects a temporary number t i for each of the rest sorted sub-channels by selecting a maximum of a zero and a calculated number c i =t 1 −d i for each of the sorted sub-channels, i.e. t i =max{0,c i }=max{0,t i −d i }. All the t i values for the rest sorted sub-channels are equal to zero at this moment. After that, the selection module 141 selects the minimum of the temporary number t i and a reference value, i.e. b =6 as the number of bits b i for each of the sorted sub-channels, i.e. b i =min{t i , b }. At this moment, b 1 =1, while the other b i values are all 0.

Next, the calculation module 13 calculates the summation of the numbers of bits of the sorted sub-channels, i.e.

B = ∑ i = 1 N ⁢ b i = ∑ i = 1 29 ⁢ b i ,

which is 1 because b 1 =1 and the rest b i values are zero. The comparison module 142 compares the summation B with the predetermined number B req =58. The process module 143 processes the number of bits b i of each sub-channels according to the compared result. In other words, the operation is correlated with the result of whether the summation is smaller than, greater than, or equal to B req .

At this moment, the summation B, i.e. 1, is smaller than the predetermined number B req , i.e. 58. The increase module 143 b increases the temporary number of the first sorted sub-channel t 1 by one, resulting in t 1 =2. In response to the increase of t 1 , the calculation module 13 repeatedly calculates the calculated number c i =t 1 −d i for each of the rest sorted sub-channels, while the selection module 141 repeatedly selects t i =max{0,c i } for each of the rest sorted sub-channel. The selection module 141 further repeatedly selects b i =min{t 1 , b } for each of the sorted sub-channels, while the calculation module 13 repeatedly calculates the summation

B = ∑ i = 1 N ⁢ b i = ∑ i = 1 29 ⁢ b i .

Then, the comparison module 142 repeatedly compares the summation with the predetermined number B req , so that the process module 143 can repeatedly process the number of bits of each of the sub-channels according to the compared result. The aforementioned operations will be repeated until the summation B is not smaller than the predetermined number B req .

Assuming that the temporary number of the first sorted sub-channel has been increased to 7, i.e. t 1 =7, the aforementioned operations are visualized in FIG. 2B with t 1 =7. In FIG. 2B , the horizontal axis represents the sorted sub-channels, while the vertical axis represents the number of bits. Although the vertical bars indicate the number of bits, they do not indicate the number of bits that are assigned to the sorted sub-channels. Instead, the portions of the vertical bars bound in the rectangle 22 represent the number of bits b i assigned to the sorted sub-channels. The summation of the number of bits comprised in the rectangle 22 is the summation B, which equals 49 at this moment. Meanwhile, the bits comprised in the rectangle 21 represent t i . Since the summation of the bits is smaller than the predetermined number B req =58, the rectangles 21 , 22 continue moving downward as indicated by the arrow 20 , i.e. increasing t i .

Next, the increase module 143 b increases t 1 to 8. Then, the calculation module 13 derives c 2 =7, c 3 =7, c 4 =6, c 5 =6, c 6 =6, c 7 =4, c 8 =4, c 9 =4, c 10 =4, c 11 =2, c 12 =2, c 13 =2, c 14 =2, c 15 =−3, c 16 =−4, c 17 =−4, c 18 =−4, c 19 =−4, c 20 =−4, c 21 =−4, c 22 =−4, c 23 =−5, c 24 =−5, c 25 =−5, c 26 =−5, c 27 =−5, c 28 =−5, and c 29 =−5, the selection module 141 derives t 2 =7, t 3 =7, t 4 =6, t 5 =6, t 6 =6, t 7 =4, t 8 =4, t 9 =4, t 10 =4, t 11 =2, t 12 =2, t 13 =2, t 14 =2, t 15 =0, t 16 =0, t 17 =0, t 18 =0, t 19 =0, t 20 =0, t 21 =0, t 22 =0, t 23 =0, t 24 =0, t 25 =0, t 26 =0, t 27 =0, t 28 =0, and t 29 =0, and the selection module 141 derives b 1 =6, b 2 =6, b 3 =6, b 4 =6, b 5 =6, b 6 =6, b 7 =4, b 8 =4, b 9 =4, b 10 =4, b 11 =2, b 12 =2, b 13 =2, b 14 =2, b 15 =0, b 16 =0, b 17 =0, b 18 =0, b 19 =0, b 20 =0, b 21 =0, b 22 =0, b 23 =0, b 24 =0, b 25 =0, b 26 =0, b 27 =0, b 28 =0, and b 29 =0 in sequence. Then, the calculation module 13 calculates the summation, which equals 60. The comparison module 142 compares the summation B=60 with the predetermined number B req =58. FIG. 2C illustrates the corresponding information when t 1 =8. The bits comprised in the rectangle 23 represent t i , while the bits comprised in the rectangle 24 represent the number of bits b i assigned to the sorted sub-channels.

Since the summation B is greater than the predetermined number B req , the process module 143 processes an alternative approach. That is, the first embodiment enters the second stage, i.e. removing stage. First, the group module 141 a groups the sub-channels with the same number of bits b i into a plurality of groups. To be more specific, the group module 141 a groups S 1 , S 2 , S 3 , S 4 , S 5 , and S 6 into a group G 1 , groups S 7 , S 8 , S 9 , and S 10 into a group G 2 , and groups S 11 , S 12 , S 13 , and S 14 into a group G 3 . Then, the selection module 141 selects the sub-channel with the smallest CNR from each of the groups to derive the candidates. That is, the selection module 141 selects S 6 from group G 1 , S 10 from group G 2 , and S 14 from group G 3 as the candidates. The calculation module 13 then calculates a power reduction value for each of the candidates using the following equation:

Δ ⁢ ⁢ P j - = Γ C ⁢ ⁢ N ⁢ ⁢ R j ⁢ 2 b j - 1 ,

wherein j indicates the index of the candidates and

Γ = 1 1.6 ⁢ ln ⁡ ( 0.2 B ⁢ ⁢ E ⁢ ⁢ R )

is constant under the bit error rate (BER) constraint. The decrease module 141 b decreases the number of bits of the candidates with the greatest power reduction value by one. Assuming that the candidate with the greatest power reduction value is S 6 , the number of bits of S 6 is decreased to 5 with the decrease module 141 b . Then, the calculation module 13 calculates the summation, B, of the number of bits of the sorted sub-channels again and derives B=59. The comparison module 142 compares the summation with the predetermined number again so that the process module 143 can process the number of bits of each sub-channel according to the compared result.

Because the summation, 59, is still greater than the predetermined number 58, the selection module 141 repeatedly selects the sub-channel with the smallest quality value from each of the groups to derive the candidate again, i.e. selecting S 5 from group G 1 , S 10 from group G 2 , and S 14 from group G 3 . The calculation module 13 then repeatedly calculates the power reduction value for each of the candidates again. Likewise, the decrease module 141 b repeatedly decreases the number of bits of the candidate with the greatest power reduction by one. This time, the decrease module 141 b decreases the number of bits of S 5 to 5. Then, the calculation module 13 calculates the summation of the number of bits of the sorted sub-channels, which equals 58. The comparison module 142 compares the summation with the predetermined number again so the process 143 module can process the number of bits of each of the sub-channels according to the compared result.

Now, because the compared result of summation B is equal to the predetermined number B req , the load module 143 a loads the numbers of bits, b 1 =6, b 2 =6, b 3 =6, b 4 =6, b 5 =5, b 6 =5, b 7 =4, b 8 =4, b 9 =4, b 10 =4, b 11 =2, b 12 =2, b 13 =2, b 14 =2, b 15 =0, b 16 =0, b 17 =0, b 18 =0, b 19 =0, b 20 =0, b 21 =0, b 22 =0, b 23 =0, b 24 =0, b 25 =0, b 26 =0, b 27 =0, b 28 =0, and b 29 =0, into the corresponding sub-channels. Then, the interface 15 transmits the predetermined number of bits.

Since the difference values are calculated at the very beginning in the loading stage, the bits allocated to all the sorted sub-channels are simply updated according to the difference values. This updating approach in the loading stage has two significant indications. The first indication is that all the sorted sub-channels are updated together, while the second indication is that the updating is achieved by simple calculations. After several iterations, when the summation of the numbers of bits is not smaller than the predetermined number (i.e. the required data rate B req ), the loading stage finishes. At this moment, the number of bits b i assigned to each of the sub-channels is equal to or is one-bit greater than the number derived by the optimal methods (bit-loading method and bit-removal method of the prior art). Although the removal stage requires the calculation of the power reduction values for each of the candidates, it is still efficient because the candidate sizes are extremely small. The present invention requires N+1 logarithmic operations, N exponential operations, and 2N+3 multiplications. Consequently, the present invention is able to load the predetermined number of bits B req into the N sub-channels.

FIG. 3A illustrates the flowchart of the second embodiment of the present invention, which is a method for loading a predetermined number of bits into a plurality of sub-channels. First, the method executes step 301 to sort the sub-channels into a plurality of sorted sub-channels according to a quality value of each of the sub-channels. Then, step 302 is executed to calculate a difference value for each of the sorted sub-channels, except for the first sorted sub-channels, according to the corresponding quality values according to

d i = ⌊ log 2 ⁡ ( C ⁢ ⁢ N ⁢ ⁢ R 1 C ⁢ ⁢ N ⁢ ⁢ R i ) ⌋ ,

wherein i denotes the index of the sub-channel, CNR i denotes the quality value of the i th sorted sub-channel, and d i denotes the difference value. Then, 303 ˜ 319 are executed to decide a number of bits for each of the sorted sub-channels according to the difference values, wherein a summation of the numbers is equal to the predetermined number.

More specifically, step 303 decides a temporary number for the first sorted sub-channel. Next, step 304 calculates a calculated number for each of the rest sorted sub-channels by subtracting the corresponding difference value from the number of bits of the first sorted sub-channel. After that, step 305 selects a maximum value of zero and the calculated number as a temporary number for each of the rest sorted sub-channels. Then, step 306 selects a minimum of the temporary number and a reference value as the number of bits for each of the sorted sub-channels, wherein the reference value is the maximum number of bits that each of the sub-channel is adapted to carry. The method further executes step 307 to calculate the summation of the numbers of bits of the sorted sub-channels. Then, step 308 compares the summation with the predetermined number. Lastly, step 309 processes the number of bits of each of the sub-channels according to the compared result.

More specifically, step 309 comprises steps 310 ˜ 319 as illustrated in FIG. 3B . First, step 310 determines whether the summation is smaller than the predetermined number. If so, step 311 increases the temporary number of the first sorted sub-channel by one. Then, the method proceeds to step 304 . If the result of step 310 indicates the summation is not smaller than the predetermined number, step 312 determines whether the summation is equal to the predetermined number. If so, step 313 loads the numbers of bits into the sub-channels. If not, i.e. the summation is greater than the predetermined number, the method executes step 314 to determine whether the sub-channels have been grouped. If the sub-channels have not been grouped yet, the method executes step 315 to group the sub-channels with the same number of bits into a plurality of groups. Next, step 316 selects the sub-channel with the smallest quality value from each of the groups to derive a plurality of candidates. If the sub-channels have been grouped in step 314 , the method directly proceeds to step 316 . Next, the method proceeds to step 317 to calculate a power reduction value for each of the candidates. Step 318 decreases the number of bits of the candidate with the greatest power reduction value by one. Next, step 319 calculates the summation of the number of bits of the sorted sub-channels. Then, the method proceeds to step 312 again.

In addition to the steps illustrated in FIG. 3A and FIG. 3B , the second embodiment is able to execute all the operations and functions described in the first embodiment. Those skilled in the art can directly understand how the second embodiment can execute the operations and functions based on the aforementioned first embodiment. Consequently, redundant descriptions for the operations and functions are not repeated herein.

The above disclosure is related to the detailed technical contents and inventive features thereof. People skilled in this field may proceed with a variety of modifications and replacements based on the disclosures and suggestions of the invention as described without departing from the characteristics thereof. Nevertheless, although such modifications and replacements are not fully disclosed in the above descriptions, they have substantially been covered in the following claims as appended.