HK1061125B

HK1061125B - Method and apparatus for allocating data streams onto a single channel

Info

Publication number: HK1061125B
Application number: HK04104117.6A
Authority: HK
Inventors: A.H.瓦亚诺斯; F．格里尔里
Original assignee: 高通股份有限公司
Priority date: 2000-11-15
Filing date: 2001-11-14
Publication date: 2006-08-25

Description

Method and device for allocating data streams to single channels

Technical Field

The present invention relates generally to the field of communications, and more particularly to a novel and improved system and method for allocating a large number of data streams onto a single channel.

Background

A remote station is located within the network. The remote station includes an application that generates a logical data stream. The remote station distributes the logical data streams onto a single transport stream. ONE technique FOR MULTIPLEXING data from a logical data stream ONTO a transport stream is disclosed in U.S. patent application serial No. 09/612825, published on 8.2.1999, entitled "METHOD and apparatus FOR MULTIPLEXING data streams," which is assigned to the assignee of the present invention and is incorporated herein by reference.

Selecting a scheme for allocating bits from multiple data streams onto a single channel is difficult because many factors must be considered. One factor to consider is the priority of each data stream. A high priority data stream takes precedence over a low priority data stream. Another factor to consider is the type of Transport Format Combination (TFC) that is allowed. The TFC is a combination of transmission frames that are sent out on the radio link of the remote station per time slot. A transport format has a number of blocks (i.e., one or more blocks) and a block size. It is desirable to consider the priority of the data streams and the allocation scheme of the available TFCs.

It would also be desirable to have an allocation scheme for selecting TFCs without wasting valuable space to fill the TFCs. In addition, throughput is improved when padding is not required since the TFC transmitted on the transport channel is full. Some allocation schemes fill TFCs. In these padded allocation schemes, the TFC is padded when the TFC is not completely filled with bits from the logical data stream.

Disclosure of Invention

The presently disclosed method and apparatus is directed to allocating a large number of data streams onto one data stream for transmission. An allowed TFC list is received from the network. Bits from a data stream at a logical level are coded into TFCs at the transport level according to the priority of the data stream and the available TFCs.

According to the present invention, there is provided a method of selecting a transmission frame combination when a plurality of data streams are multiplexed onto one data stream, characterized by comprising: receiving a set of transmission frame combinations from the network; and selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group can be filled with bits from the plurality of data streams.

According to the present invention there is provided a subscriber unit comprising: a memory; a plurality of applications residing in the memory, each application capable of generating a data stream, wherein each data stream comprises at least one bit; and a multiplexer for receiving each data stream, receiving a set of transmission frame combinations, and selecting a transmission frame combination from the received set according to whether at least one transmission frame combination in the received set can be filled with bits from the plurality of data streams.

According to the present invention, there is provided a base station comprising: a memory; a plurality of applications residing in the memory, each application capable of generating a data stream, wherein each data stream comprises at least one bit; and a multiplexer for receiving each data stream, receiving a set of transmission frame combinations, and selecting a transmission frame combination from the received set according to whether at least one transmission frame combination in the received set can be filled with bits from the plurality of data streams.

According to the present invention, there is provided a base station controller comprising: a memory; a plurality of applications residing in the memory, each application capable of generating a data stream, wherein each data stream comprises at least one bit; and a multiplexer for receiving each data stream, receiving a set of transmission frame combinations, and selecting a transmission frame combination from the received set according to whether at least one transmission frame combination in the received set can be filled with bits from the plurality of data streams.

According to the present invention there is provided an apparatus for selecting a combination of transmission frames when combining data from a plurality of data sources for transmission into a single data stream, comprising: a memory; and a multiplexer communicatively attached to the memory, the multiplexer to: receiving a plurality of data streams from the data source, each data stream consisting of a block of data words containing a number of data bits, a block of data words being referred to as a transmission frame; multiplexing data from the plurality of data sources onto a single data stream in a plurality of transmission frames forming a transmission frame combination: receiving a set of transmission frame combinations; and selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group is fillable with bits from the plurality of data streams.

According to the present invention there is provided a method of selecting a combination of transmission frames when combining data from a plurality of data sources for transmission into a single data stream, comprising: receiving a plurality of data streams from the data source, each data stream consisting of a block of data words containing a number of data bits, a block of data words being referred to as a transmission frame; multiplexing data from the plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination; receiving a set of transmission frame combinations; and selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group is fillable with bits from the plurality of data streams.

According to the present invention there is provided a subscriber unit for selecting a combination of transmission frames when combining data from a plurality of data sources for transmission into a single data stream, comprising: a memory; and a multiplexer communicatively attached to the memory, the multiplexer to: receiving a plurality of data streams from the data source, each data stream consisting of a block of data words containing a number of data bits, a block of data words being referred to as a transmission frame; multiplexing data from the plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination; receiving a set of transmission frame combinations; and selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group is fillable with bits from the plurality of data streams.

According to the present invention, there is provided a base station for selecting a transmission frame combination when combining data from a plurality of data sources for transmission into a single data stream, comprising: a memory; and a multiplexer communicatively attached to the memory, the multiplexer to: receiving a plurality of data streams from the data source, each data stream consisting of a block of data words containing a number of data bits, a block of data words being referred to as a transmission frame; multiplexing data from the plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination; receiving a set of transmission frame combinations; and selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group is fillable with bits from the plurality of data streams.

According to the present invention there is provided a subscriber unit for combining data from a plurality of data sources for transmission into a single data stream, comprising: means for receiving a plurality of data streams from said data source, each data stream consisting of blocks of data words containing a number of data bits, a block of data words being referred to as a transmission frame; means for multiplexing data from said plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination; means for receiving a set of transmission frame combinations; and means for selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group can be filled with bits from the plurality of data streams.

According to the present invention there is provided a base station for combining data from a plurality of data sources for transmission into a single data stream, comprising: means for receiving a plurality of data streams from said data source, each data stream consisting of blocks of data words containing a number of data bits, a block of data words being referred to as a transmission frame; means for multiplexing data from said plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination; means for receiving a set of transmission frame combinations; and means for selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group can be filled with bits from the plurality of data streams.

According to the present invention there is provided a system for communicating data, comprising: a plurality of subscriber units, comprising: a memory; and a multiplexer communicatively attached to the memory, the multiplexer to: receiving a plurality of data streams from the data source, each data stream consisting of a block of data words containing a number of data bits, a block of data words being referred to as a transmission frame; multiplexing data from the plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination; receiving a set of transmission frame combinations; and selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group can be filled with bits from the plurality of data streams; and, a plurality of base stations, including: a memory; and a multiplexer communicatively attached to the memory, the multiplexer to: receiving a plurality of data streams from the data source, each data stream consisting of a block of data words containing a number of data bits, a block of data words being referred to as a transmission frame; multiplexing data from the plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination; receiving a set of transmission frame combinations; and selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group is fillable with bits from the plurality of data streams.

In one aspect, a large number of applications provide a large number of data streams to be distributed into a single stream. Subscriber units, on the other hand, provide a large number of data streams to be allocated to a single stream of the base station. In yet another embodiment, a large number of base stations provide a large number of data streams to be multiplexed by a multiplexer in a base station controller. The multiplexer may be a processor or a processor capable of conventional multiplexing tasks such as combining multiple input data streams into one output or splitting a single input data stream into multiple output data streams. The multiplexer may also be a processor capable of making logic decisions or other operational functions.

In one aspect, a subscriber unit includes a memory in which a plurality of applications reside, each application generating a data stream, wherein each data stream includes at least one bit, and a multiplexer for receiving each data stream and uniformly distributing bits from the plurality of data streams onto a single data stream.

In one aspect, a multiplexer is used to receive each data stream and distribute bits from a large number of data streams evenly onto a single data stream according to a scale value.

In another aspect, a multiplexer is used to receive each of the plurality of data streams and to distribute bits from the plurality of data streams evenly onto the single data stream, first according to the scale values of the data streams and second according to the priority of the data streams.

In yet another aspect, a wireless communication system includes a subscriber unit, a base station coupled to the subscriber unit, and a base station controller coupled to the base station. The subscriber unit comprises a number of applications and a multiplexer, wherein each application generates a data stream as an input to the multiplexer and each data stream comprises at least one bit. The multiplexer distributes the bits from the data streams onto the individual streams according to the allowed TFC that do not need padding.

Drawings

The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein:

FIG. 1 is a schematic diagram of an exemplary cellular telephone system;

fig. 2 shows a block diagram of a mobile station and a base station in accordance with an embodiment;

3A-3B illustrate a flow diagram for eliminating TFCs according to available bits in an embodiment; and

fig. 4A-4C illustrate a flow diagram for selecting a TFC in an exemplary embodiment.

Detailed Description

An exemplary cellular telephone system encompassed by the present invention is illustrated in fig. 1. For purposes of illustration, the exemplary embodiments are set forth herein in the context of a W-CDMA cellular communication system. It is understood, however, that the present invention may be used in other types of communication systems, such as Personal Communication Systems (PCS), wireless local loops, private branch exchanges (PBX), or other known systems. Also, systems using other known multiple access schemes, such as Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA), as well as other spread spectrum systems, may use the presently disclosed methods and apparatus.

As shown in fig. 1, a wireless communication network 10 typically includes a number of mobile stations (also known as mobile objects, subscriber units, remote stations, or user equipment) 12a-12d, a number of base stations (also known as Base Transceiver Stations (BTSs) or node bs) 14a-14c, Base Station Controllers (BSCs) (also known as radio network controllers or packet control functions 16), Mobile Station Controllers (MSCs) or switches 18, Packet Data Serving Nodes (PDSNs) or inter-network interworking functions (IWFs) 20, a Public Switched Telephone Network (PSTN)22 (typically a telephone company), and an Internet Protocol (IP) network 24 (typically the internet). For simplicity, 4 mobile stations 12a-12d, 3 base stations 14a-14c, one BSC16, one MSC 18, and one PDSN 20 are shown. One of ordinary skill in the art will appreciate that any number of mobile stations 12, base stations 14, BSCs 16, MSCs 18, and PDSNs 20 may be present.

In one embodiment, the wireless communication network 10 is a packet data service network. The mobile stations 12a-12d may be any of a number of different types of wireless communication devices such as, for example, a portable telephone, a cellular telephone that is connected to a laptop computer running an IP-based web browser application, a cellular telephone with an associated hands-free car kit, a Personal Digital Assistant (PDA) running an IP-based web browser application, a wireless communication module incorporated into a portable computer, or a fixed location communication module such as may be included in a wireless local loop or meter reading system. In the most general embodiment, the mobile station may be any type of communication unit.

The mobile stations 12a-12d may advantageously be configured to engage in one or more wireless packet data protocols as described, for example, in the EIA/TIA/IS-707 standard. In a particular embodiment, the mobile stations 12a-12d generate IP packets destined for the IP network 24 and encapsulate the IP packets into frames using a Point-to-Point protocol (PPP).

In one embodiment, the IP network 24 is coupled to a PDSN 20, the PDSN 20 is coupled to a MSC 18, the MSC 18 is coupled to the BSC16 and the PSTN 22, and the BSC16 is coupled to the base stations 14a-14c by wireline for transporting voice and/or data packets in any of several known protocols, including E1, T1, Asynchronous Transfer Mode (ATM), IP, PPP, frame Relay, HDSL, ADSL, or xDSL, among others. In an alternative embodiment, the BSC16 is coupled directly to the PDSN 20, while the MSC 18 is not coupled to the PDSN 20. In one embodiment, the mobile stations 12a-12d communicate with the base stations 14a-14c over a Radio Frequency (RF) interface defined in a third Generation partnership project 2 "3 GPP 2" entitled "Physical Layer Standard for cdma 2000SpreadSpectrum Systems," published as TIA/EIA/IS-2000-2-A (draft, revision 301 (11/19 1999) (hereinafter "cdma 2000"), entitled C.P2000-A, TIA PN-4694, 3GPP2, which IS hereby incorporated by reference in its entirety.

During typical operation of the wireless communication network 10, the base stations 14a-14c receive and demodulate sets of reverse link signals from respective mobile stations 12a-12d engaged in telephone calls, web browsing, or other data communications. Each reverse link signal received by a given base station 14a-14c is processed in the base station 14a-14 c. Each base station 14a-14c may communicate with a large number of mobile stations 12a-12d by modulating and transmitting sets of forward link signals to the mobile stations 12a-12 d. For example, as shown in fig. 1, the base station 14a communicates with first and second mobile stations 12a, 12b simultaneously, while the base station 14c communicates with third and fourth mobile stations 12c, 12d simultaneously. The resulting packets are forwarded to the BSC16, which provides call resource allocation and mobility management functions including the handoff of a call for a particular mobile station 12a-12d from one base station 14a-14c to another base station 14a-14 c. For example, the mobile station 12c is communicating with two base stations 14b, 14c simultaneously. Eventually, when the mobile station 12c moves far enough away from one of the base stations 14c, the call will be handed off to the other base station 14 b.

If the transmission is a conventional telephone call, the BSC16 will send the received data to the MSC 18, which provides other routing services for interfacing with the PSTN 22. If the transmission is a packet-based transmission, such as a data call directed to the IP network 24, the MSC 18 will send the data packet to the PDSN 20, which will send the packet to the IP network 24. Alternatively, the BSC16 will send the packets directly to the PDSN 20 which sends the packets to the IP network 24.

The wireless communication channel through which the information signal travels from the mobile station 12 to the base station 14 is referred to as the reverse link. The wireless communication channel through which the information signal travels from the base station 14 to the mobile station 12 is referred to as the forward link.

CDMA systems are typically designed to comply with one or more standards. Such standards include the "TIA/EIA/IS-95-B Mobile Station-Base Station compatibility Standard for Dual-Mode Wireless Spread Spectrum Cellular System" (IS-95 standard), "TIA/EIA/IS-98 Recommended Minimum Standard for Dual-Mode Wireless Spread Spectrum Cellular Mobile System" (IS-98 standard), the standards proposed by the Association of the name "3 rd Generation Partnership Project" (3GPP) and included in the set of documents including the documents 3G TS 25.211, 3G TS 25.212, 3GTS 25.213 and 3G TS 25.214 (W-CDMA standard), and "TIA/EIA/IS-CD code 2000High Data interface Standard" (Inter856 HDR standard). New CDMA standards are proposed and adopted on a continuing basis. These standards are all incorporated herein by reference.

More information about code division multiple access COMMUNICATION SYSTEMs is disclosed IN U.S. patent No. 4901307 entitled "SPREAD SPECTRUM COMMUNICATION SYSTEM USING SATELLITE signals" and U.S. patent No. 5103459 entitled "SYSTEM AND METHOD FOR GENERATING signals IN ACDMA cell layer SYSTEM", both of which are assigned to the assignee of the present invention and incorporated herein by reference.

CDMA 2000 IS compatible with IS-95 systems in many ways. For example, in cdma 2000 and IS-95 systems, each base station time synchronizes its operation with the other base stations in the system. Generally, the base station synchronizes operation with an international standard-time reference such as Global Positioning System (GPS) signaling; however, other mechanisms may be used. Each base station within a given geographic region is assigned a common sequence offset of a pseudo-noise (PN) pilot sequence based on a synchronization time reference. For example, according to IS-95, having 2¹⁵A PN sequence that is a chip and repeats every 26.67 milliseconds (ms) is transmitted by each base station as a pilot signal. The pilot PN sequence is transmitted by each base station at one of 512 possible PN sequence offsets. Each base station continuously transmits a pilot signal, which enables the mobile station to identify the base station's transmissionsAnd other functions.

In an exemplary embodiment, the mobile station communicates with the base station using wideband code division multiple access (W-CDMA) techniques. Base stations in a W-CDMA system operate asynchronously. That is, the W-CDMA base stations do not share a common universal time reference. The different base stations are not time aligned. Thus, although a W-CDMA base station has a pilot signal, the W-CDMA base station cannot be identified only by its pilot signal offset. Once the system time of one base station is determined, it cannot be used to estimate the system time of a neighboring base station. For this reason, a mobile station in a W-CDMA system uses a three-step PERCH acquisition procedure to synchronize with each base station in the system. Each step in the acquisition procedure identifies a different code in the frame structure called the PERCH channel.

In the exemplary embodiment, the mobile station has a large number of applications. Applications reside in the mobile station and each application generates a respective data stream. An application may generate more than one data stream.

Fig. 2 shows a block diagram of the mobile station 12 and the base station 14 according to an example embodiment. The mobile station 12 includes voice 32, signaling 34, email 36 and web application 38 residing in memory 49 of the mobile station 12. Each application, voice 32, signaling 34, email 36 and web application 38, produces a respective data stream 40, 42, 44, 46, respectively. These data streams are multiplexed by multiplexer module 48 onto one data stream called transport stream 50. The transport stream 50 is transmitted on the reverse link to a base transceiver station 14(BTS), also referred to simply as a base station.

Each data stream 40-46 has a priority. The multiplexer module 48 places bits from the data stream on the logical level into the TFCs on the transport level according to the priority of the data stream and the available TFCs that do not need to be filled. Other systems fill TFCs that are not filled with bits from the data stream. However, embodiments of the present invention do not fill TFCs.

In the exemplary embodiment, multiplexer module 48 operates within the Medium Access Control (MAC) layer and obtains data flow priorities from a higher network layer. The MAC layer defines procedures for receiving and transmitting on the physical layer.

As will be apparent to one of ordinary skill in the art, the data streams 40-46 may be prioritized by any prioritization scheme known in the art, such as a first-in-first-out (FIFO) method, a last-in-first-out (LIFO) method, and a Shortest Job First (SJF) method. The multiplexer module 48 may operate at many network levels, as will be apparent to those of ordinary skill in the art.

In another embodiment, the multiplexer module 48 is implemented in hardware. In yet another embodiment, the multiplexer module 48 is implemented in a combination of software and hardware. As will be apparent to one of ordinary skill in the art, the multiplexer module 48 may be implemented by any combination of software and hardware.

In an embodiment, the multiplexer module 48 uses a distribution algorithm. For any given time slot, the allocation algorithm removes the TFC that needs to be filled. Thus, only TFCs that do not need padding are valid. For a given slot, the TFC that needs to be filled is invalid.

If the allocation algorithm does not remove the invalid TFC, it may select the TFC that requires padding. Selecting a TFC that allows transmission of most of the high priority bits may result in selection of an invalid TFC. The TFC may be invalid because the selected TFC results in bits of high priority being transmitted, but there are available bits in the TFC for other logical channels of low priority. To avoid selecting an invalid TFC, the allocation algorithm of an embodiment requires that the invalid TFC be removed before the TFC is selected.

A set of allowed TFCs is received from the network. This group is called a Transport Frame Combination Set (TFCS). The TFCs in the TFCs is allowed in the sense that the network allows the TFC to be transmitted over the network.

In one embodiment, the allocation algorithm has at least three steps as shown below:

(1) setting S1 to a set of TFCS in the TFCS that can be used according to the current maximum transmitter power;

(2) setting S2 to a set of TFCs in S1 that can be used according to currently available bits from a different logical channel assumed not to allow introduction of a "padding" block; and

(3) the TFC is chosen from S2 that allows transmission of most of the high priority bits.

In another embodiment, step (2) and step (1) are inverted. Yet another embodiment includes steps (2) and (3), but does not include step (1). Each step is set forth in more detail below.

In step (1), the TFCs are removed from the set of allowed TFCs according to power requirements. Each TFC requires a certain amount of power in order to be transmitted. The power requirement for each TFC is calculated. TFCs requiring higher transmission power than can be currently issued are removed. TFCs having a required transmission power lower than the currently possible transmission power remain.

The second step is to remove the remaining TFCs that require padding the block according to the available bits. The TFC with the available bits is removed. The free blocks of each TFC are checked.

BS_ijIs block size, and BSS_ijIs the block size in the ith TFC for the jth transport channel (in the allowed TFCs). Suppose B_ikIs the buffer occupancy of the kth logical channel corresponding to the ith transport channel. It is assumed that the block size and block group size are adjusted to accommodate the MAC header and therefore have a strict correspondence to buffer occupancy. A TFC may only be acceptable if it does not contain more bits than are available for any transport channel. The remaining pseudo code for removing the TFC according to the available bits is shown below:

1. let S2 be S1.

2. It is assumed that there are n transport channels numbered 1 to n.

3. Let i equal to 1. This will be the subscript of all transport channels.

4. It is assumed that Sb is a block size group in an arbitrary TFC present in S2 of the ith transport channel.

5. The block size Sb is selected from Sb.

6. Let St be the set of m TFCs in S2 with block size BS of the ith transport channel, numbered from 1 to m.

7. Let j equal 1. This will be a subscript of the TFC in St.

8. And (3) calculating:

9. if BSS_jiIf T is less than or equal to T, the operation is switched to 11. Wherein BSS_jiThe ith transport channel corresponding to the jth TFC in St.

10.S2＝S2-{TFC_jAnd j, wherein j of TFCj to St is the jth TFC.

11.j+＝1.

12. If j is less than or equal to m, go to step 9.

13. Let Sb ═ Sb- { BS }.

14. If Sb ≠ { φ }, then proceed to step 5.

15. Let i + ═ 1.

16. If i is less than or equal to n, go to step 4.

17. The algorithm ends and the effective TFC is in S2.

Fig. 3A-3B illustrate a flow diagram for TFC removal based on available bits in one embodiment. Group S2 is set to S1 (100). S1 is a set of allowed TFCs that do not require more power than can be transmitted. Assume that there are n transport channels, numbered from 1 to n (102). The index i is initialized (104). The index i is the index of the transmission channel. It is assumed that Sb is a group of all block sizes existing in an arbitrary TFC in the group S2 of the ith transport channel (106). The block size BS (10) is selected from the group Sb8). Let St be the set of m TFCs in S2 with block size BS of the ith transport channel, numbered from 1 to m (110). The subscript J is initialized (112). The index j is an index of the TFCs in the group St. Calculating a threshold value:(114). The threshold T is used to check if there is too much space in the TFC. BSS if block size_jiT (116), subscript j is incremented by 1(118), otherwise there is so much space that TFCs would require padding blocks and removing TFCs from set S2. (120) And subscript j plus 1 (118). If there are more TFCs to process, i.e., j ≦ m, then return and check if the block size Bss is large_jiT ≦ 116, otherwise the block size is subtracted from the input from group Sb having that block size (124). If Sb is not null (126), return and select another block size BS (108), otherwise subscript i plus 1 (128). If all transport channels are unprocessed, i ≦ n (130), then Sb is assumed to be a group of all block sizes in any TFC present in the group S2 for the next transport channel (106). If i > n, all invalid TFCs are removed from the set of available TFCs that do not require more power than can be transmitted. The valid TFC is in set S2.

In one embodiment, all TFCs (on the ith transport channel) with the same block size are grouped into S2. In another embodiment, TFCs having the same block size do not have to be grouped together. In this embodiment, T is calculated each time a different TFC is examined.

The third step is the selection of the optimal TFC. Bits from the logical data stream are assumed to be loaded into the TFC. The loaded TFCs are compared according to the amount of high priority data they contain.

There are n priorities, from P₁To P_n，P₁Is the highest priority. Assume that there are q TFCs numbered from 1 to q in S2. A variable NOB (number of bits) is created for each TFC in S2 and a variable SAS (space still available) is created for each transport channel on each TFC. All SAS should be initialized to the corresponding TFC block group size. NOB_iAnd SAS_jiIs a variable of the ith TFC and the jth transport channel in S2. L is_ijIs priority P_iThe jth logical channel of (1). The following algorithm may then be performed:

1. let S3 be S2.

2. Let i equal to 1. This will be a subscript to the priority.

3. The NOB of all TFCs in S3 is initialized to 0.

4. Let m be the number of logical channels with priority Pi.

5. Let j equal 1. This will be the subscript of the logical channel on the current priority.

6. Suppose S_ijIs a logical channel L_ijThe number of available bits.

7. Assume that 1 is a transport channel on which logical channel j is mapped.

8. Let k equal to 1. This will be the subscript of the TFC in S3.

9. If it isGo to step 13.

10.NOB_k+＝SAS_k1。

11.SAS_k1＝0。

12. Go to step 15.

(also possible to carry out: NOB_k+＝B_ij. But this makes the results sequentially relevant. )

15.k+＝1。

16. If k is less than or equal to q, go to step 9.

J + ═ 1; a logical channel.

18. If j is less than or equal to m, go to step 6.

19. The NOB is left as the highest TFC in S3.

20. If there is no TFC in S3, go to the next time slot.

21. If there is a single TFC in S3, the algorithm is complete. A single TFC is used. Go to the next slot.

I + ═ 1; priority level

23. If i is less than or equal to n, go to step 3.

24. A TFC is arbitrarily selected in S3. Go to the next slot.

Fig. 4A-4C illustrate a flow diagram for selecting a TFC in an exemplary embodiment. Group S3 is set to group S2 of the active TFC group (140). Set S3 should provide a set of TFCs that can be selected for transmission. The index i of the priority is initialized (142). There is one NOB variable for all TFCs in group S3. NOB represents the number of bits. The NOB variable for all TFCs in set S3 is initialized to 0 (144). Assume m is priority P₁The number of logical channels (146). The subscript J of the logical channel on the current priority is initialized to 1 (148). Suppose B_ijIs a logical channel L_ijIs determined (150). Logical channels are mapped onto transport channels. 1 is the transport channel (152) on which logical channel j is mapped. The index k for the TFC in set S3 is initialized to 1.

If in filling B_ijThere is still available space behind it, i.e.,then NOB will be_kIncrease ofAnd from the SAS_k1Reduction ofThen, subscript k is incremented by 1 (166). If in filling B_ijThen no space is available, the number of bits NOBk is increased by SAS_k1(162) And will SAS_k1Reset to 0 (164). Subscript k plus 1 (166). If the TFC in S2 is not processed for the logical channel, i.e., k ≦ q (168), return to filling more TFCs, i.e.,if the TFC in S2 and for the logical channel is processed, the index j is incremented by 1 (170). If j is less than or equal to m, return and assume B_ijIs a logical channel L_ijIs determined (150). Otherwise, the TFC is output for the highest NOB in the S3 group. If there is a single TFC in S3 (180), the single TFC is used (182). Go to the next slot (178). If there is more than one TFC in S3, the index i is increased by 1 (184). If i ≦ n (186), return and initialize the NOB variables for all TFCs in S3 to 0(144) and continue the algorithm. Otherwise, all transport channels have been processed. One TFC (188) in S3 may be arbitrarily selected for transmission. Go to the next slot (178).

As will be apparent to one of ordinary skill in the art, the TFC algorithm may be applied to other interconnections between network modules. It can be applied to any situation where a module has a large number of inputs and produces a multiplexed output from these large number of inputs. For example, a multiplexer module is located in the BTS, which multiplexes data streams from a large number of mobile stations and generates a multiplexed data stream to be transmitted to the BSC.

Thus, a novel and improved method and apparatus for multiplexing a plurality of data streams onto one data stream is disclosed. Those of skill would appreciate that the various illustrative logical blocks, modules, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. Various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. The skilled person will recognize the interactivity of the hardware and software in these cases and how best to implement the described functionality for each particular application. By way of example, implementation or execution of the various illustrative logical blocks, modules, and algorithm steps described in connection with the embodiments described herein may be: a processor executing a set of firmware instructions, an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components such as registers, any conventional programmable software module and a processor, or any combination of devices for performing the functions described herein. The multiplexer is preferably a microprocessor, but in the alternative, the multiplexer may be any conventional processor, controller, microcontroller, or state machine. The application program may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. As shown in fig. 2, the base station 14 is preferably coupled to the mobile station 12 to read information from the base station 14. The memory 49 may be integrated with the multiplexer 48. The multiplexer 48 and memory 49 may reside in an ASIC (not shown). The ASIC may reside in telephone 12.

The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims

1. A method for selecting a combination of transmission frames when multiplexing a plurality of data streams onto one data stream, comprising:

receiving a set of transmission frame combinations from the network; and

a transmission frame combination is selected from the received group based on whether at least one transmission frame combination in the received group can be filled with bits from the plurality of data streams.

2. The method of claim 1, further comprising padding the selected transmission frame combination with bits from the plurality of data streams.

3. The method of claim 2, further comprising scheduling the selected transmission frame combination for transmission.

4. The method of claim 2, further comprising allocating the transport frame combinations onto a single transport stream.

5. The method of claim 2, wherein selecting the transmission frame combination is also based on a priority of the plurality of data streams.

6. The method of claim 2, further comprising comparing the selected transmission frame combination to other transmission frame combinations from the group of transmission frame combinations.

7. The method of claim 6, wherein the selected transport frame combination contains more bits from the highest priority data stream than other transport frame combinations in the transport frame combination set.

8. The method of claim 6, wherein the selected transport frame combination contains more high priority bits from the bulk data stream than other transport frame combinations in the transport frame combination set.

9. A subscriber unit, comprising:

a memory;

a plurality of applications residing in the memory, each application capable of generating a data stream, wherein each data stream comprises at least one bit; and

a multiplexer for receiving each data stream, receiving a set of transmission frame combinations, and selecting a transmission frame combination from the received set based on whether at least one transmission frame combination in the received set can be filled with bits from the plurality of data streams.

10. The subscriber unit of claim 9, wherein the multiplexer fills the selected transmission frame combination with bits from the plurality of data streams.

11. The subscriber unit of claim 10 wherein the multiplexer is configured to schedule the selected combination of transmission frames for transmission.

12. The subscriber unit of claim 10, wherein the multiplexer is configured to distribute the transport frame combinations onto a single transport stream.

13. The subscriber unit of claim 10, wherein the multiplexer is configured to select a transmission frame combination based on a priority of the data stream.

14. The subscriber unit of claim 10, wherein the multiplexer is operative to compare the selected transmission frame combination with other transmission frame combinations from the group of transmission frame combinations.

15. The subscriber unit of claim 14, wherein the multiplexer is configured to select a transmission frame combination that contains more bits from a highest priority data stream of the plurality of data streams than other transmission frame combinations of the transmission frame combination set.

16. The subscriber unit of claim 14, wherein the multiplexer is configured to select a transmission frame combination that contains more high priority bits from the bulk data stream than other transmission frame combinations in the transmission frame combination set.

17. A base station, comprising:

a memory;

18. The base station of claim 17, wherein the multiplexer is configured to fill the selected combination of transmission frames with bits from the plurality of data streams based on priorities of the plurality of data streams.

19. A base station controller, comprising:

a memory;

20. The base station of claim 19, wherein the multiplexer is operative to fill the selected transmission frame combination with bits from the plurality of data streams based on priorities of the plurality of data streams.

21. An apparatus for selecting a combination of transmission frames when combining data from a plurality of data sources for transmission into a single data stream, the apparatus comprising:

a memory; and

a multiplexer communicatively attached to the memory, the multiplexer to:

receiving a plurality of data streams from the data source, each data stream consisting of a block of data words containing a number of data bits, a block of data words being referred to as a transmission frame;

multiplexing data from the plurality of data sources onto a single data stream in a plurality of transmission frames forming a transmission frame combination:

receiving a set of transmission frame combinations; and the number of the first and second groups,

22. The apparatus of claim 21, wherein the multiplexer also fills the selected transmission frame combination with bits from the plurality of data streams.

23. The apparatus of claim 22, wherein the multiplexer is also for scheduling transmission frame combinations for transmission.

24. The apparatus of claim 22, wherein the multiplexer is also for allocating combinations of transport frames onto a single transport stream.

25. The apparatus of claim 22, wherein the multiplexer is also configured to select a transmission frame combination based on a priority of the plurality of data streams.

26. The apparatus of claim 22, wherein the multiplexer is also for comparing the selected transport frame combination with other transport frame combinations in the received set of transport frame combinations.

27. The apparatus of claim 26, wherein the multiplexer also selects the transmission frame combination based on whether the selected transmission frame combination contains more bits from the highest priority data stream than other transmission frame combinations in the received transmission frame combination set.

28. The apparatus of claim 26, wherein the multiplexer also selects the transmission frame combination based on whether the selected transmission frame combination contains more high priority bits from the bulk data stream than other transmission frame combinations in the received transmission frame combination set.

29. A method of selecting a combination of transmission frames when combining data from a plurality of data sources for transmission into a single data stream, comprising:

multiplexing data from the plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination;

30. The method of claim 29, further comprising filling the selected transmission frame combinations with bits from the plurality of data streams.

31. The method of claim 30, further comprising scheduling the selected transmission frame combination for transmission.

32. The method of claim 30, further comprising allocating a combination of transmission frames onto a single transmission stream.

33. The method of claim 30, wherein the selection of the transmission frame combination is also based on a priority of the plurality of data streams.

34. The method of claim 30, further comprising comparing the selected transmission frame combination to other transmission frame combinations in the received set of transmission frame combinations.

35. The method of claim 34, comprising selecting the transmission frame combination also based on whether the selected transmission frame combination contains more bits from the highest priority data stream than other transmission frame combinations in the received set of transmission frame combinations.

36. The method of claim 34, comprising selecting the transmission frame combination also based on whether the selected transmission frame combination contains more high priority bits from the bulk data stream than other transmission frame combinations in the received transmission frame combination set.

37. A subscriber unit that selects a combination of transmission frames when combining data from a plurality of data sources for transmission into a single data stream, comprising:

a memory; and

a multiplexer communicatively attached to the memory, the multiplexer to:

38. The subscriber unit of claim 37, wherein the multiplexer also fills the selected transmission frame combination with bits from the plurality of data streams.

39. The subscriber unit of claim 38 wherein the multiplexer is also for scheduling the selected combination of transmission frames for transmission.

40. The subscriber unit of claim 38, wherein the multiplexer is also for allocating combinations of transport frames onto a single transport stream.

41. The subscriber unit of claim 38 wherein the multiplexer also selects the transmission frame combination based on a priority of the plurality of data streams.

42. The subscriber unit of claim 38 wherein the multiplexer is also for comparing the selected transport frame combination with other transport frame combinations in the received set of transport frame combinations.

43. The subscriber unit of claim 42, wherein the multiplexer also selects the transmission frame combination based on whether the selected transmission frame combination contains more bits from the highest priority data stream than other transmission frame combinations in the received transmission frame combination set.

44. The subscriber unit of claim 42, wherein the multiplexer also selects the transmission frame combination based on whether the selected transmission frame combination contains more high priority bits from the bulk data stream than other transmission frame combinations in the received transmission frame combination set.

45. A base station that selects a combination of transmission frames when combining data from a plurality of data sources for transmission into a single data stream, comprising:

a memory; and

a multiplexer communicatively attached to the memory, the multiplexer to:

46. The base station of claim 45 wherein the multiplexer also fills the selected transmission frame combination with bits from the plurality of data streams.

47. The base station of claim 46 wherein the multiplexer is also for scheduling the selected combination of transmission frames for transmission.

48. The base station of claim 46 wherein the multiplexer is also for allocating combinations of transmission frames onto a single transmission stream.

49. The base station of claim 46 wherein the multiplexer also selects the transmission frame combination based on a priority of the plurality of data streams.

50. The base station of claim 46 wherein the multiplexer is also for comparing the selected transmission frame combination with other transmission frame combinations in the received set of transmission frame combinations.

51. The base station of claim 50 wherein the multiplexer also selects the transmission frame combination based on whether the selected transmission frame combination contains more bits from the highest priority data stream than other transmission frame combinations in the received transmission frame combination set.

52. The base station of claim 50 wherein the multiplexer also selects the transmission frame combination based on whether the selected transmission frame combination contains more high priority bits from the plurality of data streams than other transmission frame combinations in the received transmission frame combination set.

53. A subscriber unit for combining data from a plurality of data sources for transmission into a single data stream, comprising:

means for receiving a plurality of data streams from said data source, each data stream consisting of blocks of data words containing a number of data bits, a block of data words being referred to as a transmission frame;

means for multiplexing data from said plurality of data sources onto a single data stream in the form of a plurality of transmission frames forming a transmission frame combination;

means for receiving a set of transmission frame combinations; and

means for selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group can be filled with bits from the plurality of data streams.

54. A base station for combining data from a plurality of data sources for transmission into a single data stream, comprising:

means for receiving a set of transmission frame combinations; and

55. A system for communicating data, comprising:

a plurality of subscriber units, comprising:

a memory; and

a multiplexer communicatively attached to the memory, the multiplexer to:

selecting a transmission frame combination from the received group based on whether at least one transmission frame combination in the received group can be filled with bits from the plurality of data streams;

and the number of the first and second groups,

a plurality of base stations, including:

a memory; and

a multiplexer communicatively attached to the memory, the multiplexer to: