Multiple access cellular communication with circular interleaving and reduced dropped-packet runlengths

ES 2 313 717 T3

DESCRIPTION

Multiple access cellular communication with circular interleaving and reduced path lengths of lost packets.

This invention relates to methods and apparatus for distributing uplink and downlink slots in a communication system, and to communication systems.

The design of a communication system or network involves evaluating the physical constraints, for example, the characteristics of a given communication channel, and the system constraints, for example, the available bandwidth per channel, to achieve a network with characteristics desired performance, such as the reliability of the information received. Cellular systems typically require low information traffic throughput delay and high information transfer reliability and high capacity while restricting the bandwidth of each cellular frequency band.

Today's wireless networks use multiple access techniques which multiplex users together to efficiently use network resources. In particular, these networks use TDMA (time division multiple access) with FDD (frequency division duplexing) as in the pan-European GSM system (now also known as Global System for Mobile Communication) and the North American IS-54 system. , or a variant, TDMA / TDD (time division duplexing), as in the European Digital Wireless Telecommunications (DECT) system. See DJ Goodman, "Second Generation Wireless Information Networks," IEEE Trans. Veh. Tech., Vt-40, No. 2, pp. 366-374, May 1991.

For the multiple access systems described here, time frames are the basic unit of transmission. Each frame is divided into a plurality of time slots. Some slots are used for control purposes and some slots are used for information transfer as described below. Information is transmitted during the slots in the frame where the slots are assigned to a specific user. Throughout this description, it will be understood that the term "information" refers to data that represents voice, text, video, or other digital information.

Other multiple access techniques, such as PRMA (Packet Reservation Multiple Access) and RALOHA (ALOHA Reservation), recognize the burst nature of voice packets and increase system capacity by having a reservation mechanism for slots. of time. See DJ Goodman, RA Valenzuela, KT Gayliard, and B. Ramamurthi, "Multiple Access by Packet Reservation for Local Wireless Communications," IEEE Trans. Comm. COM-37, No. 8, pp. 885-890, August 1989; and SS Lam, "Packet Transmission Network - A Performance Analysis of the RALOHA Protocol," IEEE Trans. Comp., COMP-29, No. 7, pp. 596603, July 1980. Although capable of supporting a large number of users over a given channel bandwidth, these approaches have limited operating ranges, and in the case of PRMA, perform poorly under low delay constraints. In addition, PRMA techniques rely on actual voice transmission, that is, the user must be actively speaking, to distribute slots rather than relying on a separate control mechanism to distribute the slots. This allocation method leads to collisions between the data packets and thus increases the delay and reduces the throughput. Other systems recognize that in a two-way conversation, it frequently happens that only one user is active, thus making it possible to obtain a high statistical multiplexing gain even with a low number of users when the information from both communication steps is multiplexed in a common channel. See LM Paratz and EV Jones, "Voice Transmission Using an Adaptive Burst Mode Technique," IEEE Trans. Comm., COM-33, No. 6, pp. 588-591, June 1985; and S. Nanda and OC Yue, “Variable Partition Duplexing for Wireless Communications,” GLOBECOM '91, pp. 32.6.1-32.6.7. However, such systems have typically been used to dynamically vary the bandwidth allocated to two parties in a single conversation (duplex voice link). This reduces voice quality when both parties are speaking simultaneously or when their voices overlap. In addition, managing slot allocation is difficult as fractional allocation of slots is required. Thus, there is a need for a multiple access system capable of providing high quality, high capacity, low delay communications, particularly for wireless personal communication systems that compete with cable systems.

US-A-4949395 relates to a cellular mobile radio station having cells that include a base station, a plurality of radio channels, and mobile stations. When the number of simultaneous connections exceeds the available number of time slots, the connections share the available time slots according to a certain multi-frame time slot distribution scheme known to the base station and mobile stations.

The IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, vol. 3, November 29, 1993 - December 2, 1993 HOUSTON (US), pages 1649-1653, XP 000436092 WCWONG AND OTHERS, 'High-quality, low-delay time-shared duplexing wireless digital voice communications describes various strategies for digital voice communication in high capacity wireless networks. Uplink and downlink traffic are allowed to share a common channel in the described STDD scheme.

According to one aspect of this invention there is provided a method claimed in claim 1.

ES 2 313 717 T3

According to another aspect of this invention the apparatus claimed in claim 6 is provided.

According to a further aspect of this invention there is provided a communication system claimed in claim 12.

A multiple access technique is described in which the slots are dynamically distributed between the uplink and downlink users. In a preferred embodiment, a method is presented for distributing slots in a communication system adapted to communicate information in an assigned slot on uplinks and downlinks between a pair of users in a set of N pairs of users. The method generates a set of frames, where each frame contains S information slots, S = U_s + D_s + A, having U_sdistributed slots for communicating information on the uplink having D_s distributed slots for communicating information on the downlink, and having A, A> 0, unused slots. OR_s and D_s they are dynamically varied in such a way as to improve the capacity and quality of the overall system.

Another aspect of the invention involves reducing the path length of lost packets in a TDMA / TDD / SAD or TDMA / STDD system. Although the average probability of packet loss is generally low in, for example, an STDD system, packet loss events are frequently correlated such that a particular user may experience a lost packet path length corresponding to several frames or more. Packet loss can result from, for example, the use of a statistical multiplexing technique such as the detection of slow-type (SAD), fast-type (FSAD), or any other type of voice activity, or the co-channel interference (CCI). The present invention uses, for example, circular interleaving to spread lost packets over many users of the system so that a given user does not experience excessive length of lost packet travel, and thus provides a robust and over-the-top communication system. high quality.

The above-discussed features, as well as additional features and advantages of the present invention, will become apparent with reference to the following detailed description and accompanying drawings.

Brief description of the drawings

Fig. 1 illustrates the components of a cellular communication system.

Fig. 2 is a diagram of a TDMA / TDD frame format known in the prior art.

Fig. 3 is a diagram of a TDMA / TDD / SAD frame format known in the prior art.

Fig. 4 is a diagram of a Time Division Shared Duplexing (STDD) frame format.

Fig. 5 is a flow chart of the steps for distributing grooves in a frame in the present invention.

Fig. 6 is a partially time division duplexing (PSTDD) frame format diagram in the present invention.

Fig. 7 shows a finite state Markov model of slow speech activity detection (SAD) according to the prior art.

Figs 8A and 8B illustrate an exemplary circular interleaving technique using a single queue for uplink and downlink users in the present invention.

Figs 9A and 9B illustrate circular interleaving in an STDD system using separate queues for the uplink and downlink users in the present invention.

Figs 10A and 10B show modifications to the model of Fig. 7 required to provide fast speech activity detection (FSAD).

Fig. 11 shows a simplified model suitable for use in analyzing lost packet path lengths in an STDD system with FSAD.

FIG. 12 is a block diagram of an exemplary communication system with circular interleaving embodying the present invention.

FIG. 13 is a flow chart of an exemplary set of appropriate processing steps to provide circular interleaving.

Detailed description

Fig. 1 illustrates the components of a cellular or microcellular communication network. Cell 102 represents a portion of the geographic area served by the system. Inside each cell is a base station 105 which is

ES 2 313 717 T3 connected to the public telephone network. The base station 105 establishes a wireless link with the users 110i, i = 1, ... N, wishing to transmit and receive information (that is, digital data representing text, voice, video, etc.) through the telephone network. public. The wireless link between a given pair of users, 110-i and base station 105, is composed of an uplink U, to transmit information from a user to base station 105 and then to the public telephone network and a downlink D, to transmit information received by the base station from the telephone network to the user. Typically, concerns about throughput delay and efficient use of bandwidth resources in a network can be addressed by the proper design and exploitation of modulation techniques, voice coding methods, channel equalization and encoding techniques. See JJC Chang, RA Miska and RA Shober, "Wireless Technologies and Systems: An Overview," AT&T Tech. J., Vol. 72, No. 4, pp. 11-18, July / August 30 1993; TP Bursh, Jr. et al., "Digital Radio for Mobile Applications", AT&T Tech. J., Vol. 72, No. 4, pp. 19-26, July / August 1993; and N. Seshadri, CE.W. Sundberg and V. Weerackody, “Advanced Techniques for Modulation, Error Correction, Channel Equalization, and Diversity”, AT&T Tech. J., Vol. 72, No. 4, pp. 48-63, July / August 1993. For example, to minimize delay, set space diversity with a small degree of channel coding can be used. Low speed speech coders, such as ADPCM, EDPCM, or LD-CELP, and modulation methods, such as asymmetric pseudo-analog DPSK, are also well suited to reduce delay. See T. Miki, C.-EW Sundberg and N. Seshadri, "Pseudo-Analog Voice Transmission in Mobile Radio Communications Systems," IEEE Trans. Veh. Tech., Vol. 42, No. 1, pp. 69-77, February 1993. Concerns with bandwidth resources can be addressed through the proper design of a multiple access technique. The purpose of a multiple access technique is to regulate communications for several pairs of users within a cell given a limited number of available frequencies, a limited bandwidth per channel, etc. More particularly, the proper design of a multiple access system is important in setting up a high-quality, low-delay digital communication network. See generally CE. W. Sundberg and N. Seshadri, “Digital Cellular Systems for North America,” GLOBECOM '90, Vol. 1, pp. 533-537, San Diego, CA, Dec. 1990.

Fig. 2 illustrates the principle of TDMA / TDD for the purpose of comparison with other systems. Although the TDMA / TDD standard has control information embedded in the headers of the information sent in the transmitted information slots, for illustrative purposes, frame 201 is divided into three sections all of which are transmitted in the same frequency band. Control section 205 contains information which relates to call management. The uplink section 210 and the downlink section 215 are each divided into N slots. Thus, the uplink and the downlink for each pair of users can have a guaranteed slot for transmitting information. However, the capacity of the system is low since a slot is assigned to each user and no re-distribution of slots is performed if a user decides not to use (ie, transmit information during) an assigned slot.

Better utilization of network resources is obtained if voice users are statistically multiplexed through the use of voice activity detection (SAD). Fig. 3 illustrates the format of the TDMA / TDD / SAD 301 frame designated for use up to N pairs of users. The TDMA / TDD / SAD 301 framework is divided into four sections. The uplink and downlink control sections 305 and 307 contain bits for manipulating call management functions. The uplink control section 305 contains bits for handling requests for the uplink information slots. The downlink control section 307 contains bits which indicate which uplink and downlink information slots are assigned for the uplink and downlink users to send and receive information. The uplink section 310 and the downlink section 315 are also divided into slots. There is an identical number of slots, less than N, in each of the uplink and downlink sections. SAD techniques recognize that a significant portion of any information transfer, particularly a voice conversation, is made up of silent portions, and it is not necessary for any information transmission to occur, that is, even if N pairs of users are active and willing. transmit information at some point, there are chances that not all users are using their distributed slots 100% of the time. Thus, the number of slots required to satisfactorily accommodate up to N pairs of users can be significantly reduced through ongoing reassignments of slots from inactive to active users. The result is a higher capacity system (since there will be a reduced number of slots that are not transmitting information) and lower delay (since the frames can be made shorter given the reduced number of slots). However, the system typically requires that a larger portion of the frame be dedicated to the overhead (ie, the control sections). Additionally, there will be insufficient resources to accommodate all users in times of peak demand, and thus some information will be lost because there will be no slots available for data transmission and / or new pairs of users will not be allowed access to the system. .

FIG. 4 illustrates a format for frame 401 useful for practicing the invention. The invention, a multiple access system called Time Division Shared Duplexing (STDD), is designed to regulate traffic between up to N pairs of users while dynamically distributing slots between uplinks and downlinks, for example, over a base. from frame to frame. Frame 401 is divided into four sections. Call management functions are handled by separate uplink and downlink slots in uplink control section 405 and downlink control section 407, respectively, as described below. The remainder of frame 401 is divided into S slots, S = U_s + D_s + A, with U_s Distributed slots for transferring uplink and D information_s Distributed slots for transferring downlink information. A represents the number of slots, if any, not distributed. In frame 401 of Fig. 4, A = 0. The number of slots distributed between the uplink section 410 and the link section

ES 2 313 717 T3 downstream 415 may vary with each frame as indicated by partition 412. However, the total number of speech slots S remains fixed for all frames. When there are few users in the system and the total number of slots in any direction is less than S / 2, the information slots behave in a TDD manner with the S slots equally partitioned for uplink and downlink access. When the number of users increases and the number of voice slots required in both directions exceeds S / 2, the partition 412 between the uplink and downlink slots varies according to demand. The ability to share a common frequency band contributes to higher statistical multiplexing gain even for a narrowband system with a limited number of users. The value of S is typically selected based on three factors: 1) the desired quality of the information received, that is, what level of packet loss is acceptable, 2) the number of pairs of users to be accommodated, and 3) the voice activity detector accuracy, that is, how well silences and pauses in information transfers can be detected. For example, for a system with N = 32 pairs of users, 64 voice slots are required for standard TDMA / TDD while TDMA / TDD / SAD requires 46 voice slots at a high quality packet loss rate of 0.01. %. The STDD typically requires 35 voice slots that assume a frame size of 2 milliseconds at the same loss rate. The total statistical multiplex gain is a function of the exact design of the control information.

Fig. 5 is a flow chart of the steps to distribute slots. Note that all signaling functions in relation to call management in a cellular or microcellular system, including handoffs and termination, but typically no call set-up functions, are communicated through the information in the control sections. In addition, the control information also indicates the status of a transmission, that is, if a user is actively communicating information or is silent. When a user wants to send information and enters the active state in step 502, such as when he is speaking, the state information in the control slot assigned to the user requests a slot in the appropriate information section, that is, link uplink, or downlink, from the base station as shown in step 504. Typically, this can be implemented using a first in, first out (FIFO) service discipline to assign information slots to users although other disciplines such as, for example, random service, can also be used. Similarly, the base station is aware of all requests emanating from the wired end of the network, and correspondingly allocates slots in step 506. The slot assignment information is carried in the uplink control information slots for both the uplink and downlink users. Thus, it is advantageous to have the transmission of the downlink control information preceding the transmission of the downlink control information in time so as to reduce the delay. If a slot is not distributed to a user after the request, the information is lost. When the information transfer is complete, the status information is restored in step 508 and the slot is returned to a repository of unused slots in step 510. The amount of control information is dictated by the needs of the functions. call management and the frequency of transmission activity.

The use of separate information and control slots helps alleviate the overhead efficiency problem common in PRMA-type networks and allows the implementation of a simple access mechanism that works advantageously with voice activity detection while providing low access delay. The uplink control section 405 and the downlink control section 407 may each contain N control slots. However, the per frame overhead can be reduced by setting a duty cycle for the control information. For example, let the total number of control slots be 2C, where C is the number of uplink or downlink control slots, and let N (where N is a multiple of C) be the maximum number of pairs of users that can be supported. In general, C <N, and therefore only C pairs of users can communicate their control information to and from the base station in a frame period. Thus, it takes a total of K = N / C frame periods for all pairs of users to be serviced in this way, that is, K is the duty cycle to serve all users. This access mechanism ensures that all users are guaranteed the service within K frame periods. At the same time, since the acknowledgments are communicated within the same frame period, a user with a recognized reservation can immediately send their voice packets within the same frame.

Note that when a user makes a reservation for voice packages the user holds the reservation for a minimum of K frame periods. For example, if the frame period is 2 ms, N = 40, and C = 5, then the duty cycle is 8 with a cycle period of 16 ms. Of course, the larger the duty cycle, the smaller the amount of control overload information. In STDD, an appropriate cycle period is 16 ms where it is conveniently timed to the speed of voice activity detection.

Even in the STDD system there may be situations where not all the information slots are used, that is, A + 0. This reserve capacity can be used to establish calls when a new call arrives at the system. It is assumed that a new user monitors the control slots for a minimum of one cycle period to ensure the status of the information slots, that is, to determine if all the slots have been assigned. The system can then use the reservation information slots as a contention channel to inform the base station of this setup request using, for example, a random access type ALOHA. If there are a number of available slots A, where A is less than S, the new call randomly selects one of these A slots to transmit its setup request packet. This request successfully reaches the base station if no other users transmit in the same slot. If the total number of currently serviced user pairs is less than N, the new call will be serviced successfully and an acknowledgment is sent on the next available downlink control slot. The location of

ES 2 313 717 T3 this control slot also determines the position of the new call in the control cycle stream. As noted earlier, when there are few users, the STDD behaves like a TDMA / TDD / SAD system with equally distributed slots between the uplink and the downlink. In this case, the spare information slots used to establish a call should be treated as information slots so that the slots remain equally distributed until such time as conditions demand partitioning between the uplink and the backlink slots. downlink is moved. The above system is described for up to N pairs of users per carrier frequency. A number of carrier frequencies, each carrying up to N pairs of users, can be used in high traffic areas.

Although previous embodiments have focused primarily on voice transmissions, the STDD can be used for mixed traffic conditions, for example where some slots carry data and some carry voice. The STDD can also be implemented in a variable range per user mode, for example a variable voice quality mode where a large number of bits are distributed to users who require higher quality video or audio. The control channel contains the appropriate information. Thus, this method can be advantageously used where there is a broadband / narrowband information transfer between users in a pair of users. In further embodiments, demand-based dynamic slot distribution between uplink and downlink is implemented by means of frequency division where information is carried over dynamically distributed orthogonal frequency channels, or alternatively in a code division mode where the traffic is carried by means of direct sequence spread spectrum with pseudo-orthogonal codes or in combinations of time division, frequency division and code division techniques. In another embodiment, the STDD format can be used in conjunction with an asymmetric sudo-analog DPSK modulation technique to further reduce throughput delay in a communication system. Additional details regarding asymmetric pseudo-analog DPSK modulation can be found in, for example, the above-cited article by T. Miki et al. Entitled "Pseudo-Analog Voice Transmission in Mobile Radio Communication Systems".

The detailed description above has illustrated a method in which the slots in a frame are dynamically distributed between the uplink and downlink users. The method has not been limited to specific software or hardware. Instead, the method has been described in such a way that those skilled in the art can easily adapt such software or hardware as may be available or preferable.

Although the exemplary STDD techniques described above provide considerable improvements in wireless communication systems, performance may be limited in certain embodiments by factors such as co-channel interference (CCI) and lost packet path lengths.

The impact of CCI on an STDD system will now be described. Unlike a TDD technique in which fixed timeslots are distributed for both uplink and downlink transmission, an STDD technique allows time slots to be dynamically distributed for both uplink and downlink depending on the demand. A user in a given cell may therefore be transmitting information in an uplink slot at the same time that a base station in a neighboring cell FR is transmitting in a downlink slot for another user. The signals transmitted from a base station are frequently at a significantly higher power level than the signals transmitted from a mobile user, and a downlink signal transmitted in the neighboring cell FR can therefore interfere with the reception of a signal from uplink in the given cell. Because this type of CCI involves a downlink signal that interferes with the reception of an uplink signal, it is referred to herein as a "mixed" CCI. In some cases this type of interference can produce a received signal to interference (S / I) ratio at the uplink base station resulting in a lost packet. Mixed CCI in an STDD system can thus significantly increase the rate of packet loss and thus reduce the capacity of the system.

Mixed CCI generally does not arise in properly timed TDMA / TDD and TDMA / TDD / SAD systems. However, TDMA / TDD and TDMA / TDD / SAD systems can exhibit "regular" CCI arising from, for example, interference between two different downlink signals or between two different uplink signals in neighboring FR cells. If the mixed CCI is controlled or eliminated, the remaining regular CCI in an STDD system would generally not be greater than that in conventional TDMA / TDD and TDMA / TDD / SAD systems.

The effects of mixed CCI can be reduced by dynamically distributing only a subset of available slots under the STDD. Fig. 6 shows an alternative STDD frame 601.

Frame 601 includes uplink and downlink control sections 605, 607 and uplink and downlink information sections 610,615. The STDD 601 frame also includes a group of shared slots 620. Shared slots 620 represent a subset of the total information transmission slots available in frame 601. The uplink and downlink sections 610, 615 contain slots which are permanently distributed for uplink and downlink transmission, respectively. Although frame 601 is illustrated as an embodiment in which the number of unused slots A equals zero, other embodiments could include values ​​of A greater than zero. Sections 610, 615 are thus similar to sections 310, 315 in frame 301 of Fig. 3. Shared slots 620 are

ES 2 313 717 T3 dynamically distributed between uplink and downlink transmission according to demand, in a manner similar to the slot distribution in sections 410 and 415 of Fig. 4. In frame 601, by therefore, only a subset of the total available information slots are dynamically distributed, while the remaining information slots are allocated to the uplink or downlink transmission. This alternative STDD technique is here referred to as partially time-sharing division duplexing (PSTDD). Because only a subset of the available slots are dynamically distributed, the potential for mixed CCI is low. The fraction of the total available information slots that are shared is designated by a partial partition factor η and different PSTDD techniques can therefore be referred to as PSTDD (n) techniques. In a PSTDD (n) system with a total of S information slots, there are (S / 2) (1η) slots available only to uplink users, (S / 2) (1-n) slots available only to uplink users. Downlink users and the remaining Sn slots are shared between uplink and downlink users according to demand. In general, PSTDD systems with partial partitioning factors η of around 15% to 25% exhibit similar packet loss rates as corresponding STDD systems, but can provide a reduction in mixed CCI. Other partial distribution factors η could also be used.

Other techniques that can be used to reduce mixed CCI include the use of directional antennas at cell base stations and the proper organization of the direction of the slots of a given frame in a way that minimizes the possibility of a directional antenna downlink. interfering with another directional antenna uplink in a neighboring FR cell. These techniques are described in detail in US Patent Application No. Serial 08/364579 entitled "Time Division Multiple Access Cellular Communication With Dynamic Slot Distribution And Reduced Co-Channel Interference", which is assigned to the licensee of the present invention.

The remaining description will be directed primarily to the effects of the path length of lost packets in TDD and STDD systems. A packet refers to an amount of information to be communicated during a given frame slot, and can represent information to be transmitted in a downlink from a base station to a user or an uplink from a user to a base station. A TDMA system which requires a low throughput delay may lose a packet if a user is unable to get an available slot in the frame in which the packet was generated. Periods of high demand can, for example, cause multiple packets generated by the same user to be lost in succession. It is therefore preferable to provide not only a low packet loss rate for all users but also a minimal "run" of successive packet loss experienced by any given user. The latter is referred to as the lost packet path length and is here defined as the number of successive frames in which a particular user experiences a lost packet. The present invention provides techniques for reducing the path length of lost packets using circular interleaving and / or fast speech activity detection (FSAD), thereby improving system capacity. Fig. 7 shows a six-state Markov model 700 corresponding to an on-off conversation between a pair of users. The model is described in PT Brady, "A Model for Generating On-Off Voice Patterns in Two-Way Conversations," Bell Sist. Tech. Journal, Vol. 48, pp. 2445-2472, September 1969.

The six states 1 through 6 are designated in Fig. 7 as TS, TT1, TT2, ST, SS1 and SS2 depending on whether the first and second users are speaking (T) or silent (S). The SS state therefore corresponds to a situation in which both users are silent while the TT1 and TT2 states correspond to situations in which both users are talking. The states TS, TT1, TT2 and ST are here generally referred to as conversation states because in those states at least one of the users is speaking.

The average time distribution of the number of slots required in a TDD or STDD system can be used by those skilled in the art to obtain expressions for the average probability of a packet loss. Even in a system with a packet loss rate on the order of 0.01%, the conditional probability that a packet is lost in a given particular frame in which one or more packets were lost in the preceding frame can remain large, resulting over an unacceptably long lost packet path length.

The following description will assume the conventional first-in-first-out (FIFO) service of users entering a talk state from a silent state. A queue made up of users whose requests cannot be accommodated by the available slots is here referred to as a blocked queue. As will be described below, the locked queue can also be viewed as a waiting portion of a larger queue, where the larger queue includes locked users and users with assigned slots. A user experiencing dropped packets waits until one or more preceding users in the blocked queue exit a conversation state. The length of time that a user takes in the blocked queue to be accommodated by the system is designated by a random variable L, and represents the cumulative duration of the consecutive frames for which the user remains blocked, that is, the length of tour of lost packages. The value of L generally depends on the position of the user in the blocked queue as well as the way in which the preceding users in the queue are accommodated. The probability distribution of L generally depends on the number of slots S, the number of pairs of users N and the type of duplexing technique that is used, and can be estimated and / or computed in a known way using techniques based on the model. of Brady.

ES 2 313 717 T3

Even if the path length of lost packets is acceptable in certain TDMA / TDD / SAD and TDMA / STDD applications, the standard deviation of L frequently remains unacceptably high. For example, lost packet path lengths of as much as 100 or 200 frames can be observed on a system with a frame duration of 2 ms. A user experiencing a lost packet may therefore be completely locked out for a considerably long period of time. The present invention alleviates this problem by ensuring that the lost packets are substantially distributed among all users who are in the frames in which the losses occur. As a result, even during long periods of lost packets the path length of lost packets for any particular user can still be relatively short in duration.

In a preferred embodiment, circular interleaving is used to periodically shift user slot assignments by one or more slots after each frame. For example, even assuming that no user exits or enters a conversation state in a given frame and therefore the slot assignments would otherwise remain the same, each user could still be directed to transmit their packet to one or more more slots. early in the next frame. A number of exceptions could be made to this alteration in the slot assignment. For example, a user first locked out in the preceding frame may be allowed to transmit in the same slot in the next frame, since that user would no longer be experiencing a long lost packet path length. Another exception could be made for a user who pays an additional service fee to continuously maintain possession of a particular slot previously allocated to that user. Paying an additional fee can thus provide certain users with a significantly lower packet loss rate and thus higher quality communication.

Figs. 8A and 8B illustrate the operation of an exemplary circular interlacing device.

In this embodiment, the simple circular interleaving device shown can be used for both uplink and downlink slots. The following will assume that the circular interleaving device is used for uplink slots. Fig. 8A shows the distribution of a group of four available uplink time slots 800 for a number of uplink users during an n-1 frame. The uplink users A, B, C and D have been allocated slots. In this example, the demand for uplink slots is greater than the number of available uplink slots so that users E and F wait in a blocked queue 810. Fig. 8B shows the distribution of four uplink time slots 800 during the next time frame n in which user C exits a talk state and users G and H enter a talk state. Users A, B, E, F, G and H are active in frame n and require uplink slots in which to communicate information, while user C is no longer active and does not require a slot. Again, only the four uplink slots 800 are available. Users G, H, and A therefore enter a blocked queue 820. Users B and D are then allocated different time slots than those that were allocated to B and D in frame n-1. Users E and F exit the blocked queue 810 of Fig. 8A and are allocated slots in the group of available slots 800. It can be seen from Figs. 8A and 8B that users who were locked in a given frame n-1, such as users E and F, are allocated slots in the next frame n. Users who have been allocated slots during frame n-1 and remain active in frame n are then allocated any remaining slots but are shifted at least one slot position to the left in frame n. As a result of moving one slot to the left, user A, while remaining active, is unable to get a slot in frame n, and will experience a lost packet. The blocked queues 810 and 820 operate as a first in, first out (FIFO) queue in this example, but other queuing techniques could also be used. A similar circular interleaving device can be used for downlink slots.

The circular interlacing device of Figs. 8A and 8B can be implemented as a set of memory locations in which user identifiers are stored during each frame. The position of a particular user identifier in memory can indicate the uplink or downlink slot assigned to that user in the current frame, or the position of that user in a blocked queue. The blocked queues 810, 820 and the available slots 800 thus represent memory storage locations for particular user identifiers. The queue 810 or 820 and the available slots 800 could be a waiting portion and an available slot portion, respectively, of a single queue. The waiting portion and the available slot portion can be implemented as memory locations that store user identifiers. The position of users in the single queue is rotated, using appropriate control processing, in the manner previously described.

In a conventional slot assignment, users A, B, D, and E of Figs. 8A and 8B could have been assigned the slots in the pool of available slots 800 and user F would have experienced dropped packets for two consecutive frames. With the circular interleaving of the present invention, lost packets are spread across users such that users A, E, and F each experience a lost packet for only one frame.

It will be apparent to those skilled in the art that this circular interleaving can be readily applied in any of a number of different TDMA communication systems, including TDD / SAD and STDD systems. The circular interleaving of the present invention does not significantly increase the traffic throughput delay, nor does it require complex computing operations.

ES 2 313 717 T3

In a TDD / SAD system in which L is very large in relation to the number n_or of uplink packets generated during a given frame, circular interleaving provides a reduced maximum number of packets lost per user which can be approximated as:

L (nu - S / 2) / nu

For example, if (n_or - S / 2) = 1, the maximum number of packets lost per user is reduced by a factor n_or. Circular interleaving thus provides a considerable improvement in terms of system strength relative to lost packets. An exemplary TDD / SAD system in accordance with the present invention uses two circular interleaving devices of the type shown in Figs. 8A and 8B, one for the uplink packets and one for the downlink packets. As noted above, each circular interleaving device can be implemented as a single queue which directs the interleaving of the available uplink or downlink slots, respectively.

In an STDD system, separate interleaving devices are also preferably used for uplink and downlink packets. Figs. 9A and 9B show an exemplary implementation of separate circular interleaving devices for the uplink and downlink. Fig. 9A corresponds to a situation in which the number of required uplink slots Us and the number of required downlink slots Ds are both greater than or equal to S / 2, where S is the total number of available slots. In this situation, a downlink queue includes an available slot portion 900 of length S / 2 and a waiting portion 905 of length Ds-S / 2. An uplink queue includes an available slot portion 910 of length S / 2 and a waiting portion 915 of length U_s - S / 2. The uplink and downlink queue provides the circular interleaving of the uplink and downlink users, respectively, in a manner similar to that previously described in conjunction with Figs. 8A and 8B. Again, the queues can be implemented as a set of memory locations with appropriate control processing. Fig. 9A is also illustrative of operation for an exemplary TDD / SAD system with uplink and downlink circular interleaving.

Fig. 9B shows the uplink and downlink circular interleaving devices in a situation where Ds is less than or equal to S / 2, Us is greater than S / 2, and Ds + Us is greater than S. A downlink queue includes a portion of available slots 920 of length D_s. Because all downlink users are assigned slots, the downlink queue does not include a waiting portion. An uplink queue includes a portion of available slots 930 of length S-Ds and a waiting portion 935 of length Us + Ds-S. Again, the uplink and downlink queues provide circular interleaving, for example, by storing and shifting user identifiers in the manner previously described. Figs. 9A and 9B can be appropriately modified to cover other situations. For example, if U_s is less than or equal to S / 2, D_s is greater than S / 2, and D_s + U_s is greater than S, the resulting uplink and downlink queues would then be similar to the uplink and downlink queues, respectively, of Fig. 9B. In addition, the modifications to the tail lengths shown in Figs. 9A and 9B resulting from the use of the PSTDD will be readily apparent to those skilled in the art.

In an STDD system, si nu denotes the number of uplink packets generated during a given frame, and n_d denotes the number of downlink packets generated during a given frame, the average number of packets lost per user in a case in which a total of L packets are lost is approximately:

L (nu + nd - S) / (n „+ nd)

An STDD system with circular interlacing according to the present invention can thus provide improved performance relative to a STDD system without circular interlacing and a TDD / sAd system with circular interlacing.

In distributed time slot circular interleaving it could be used in conjunction with co-channel interference reduction techniques such as that described in the aforementioned US Patent Application Serial No. 08/364579. It should be noted that the use of circular interleaving to reduce maximum path lengths allows lost packet replacement techniques to be used to improve speech recovery. Additional details regarding lost packet replacement can be found in, for example, DJ Goodman, GB Lockhart, OJ Wasen and WC Wong "Lost packet replacement techniques to recover lost voice segments in voice packet communications" , IEEE Trans. on Communications, Vol. 33, pp. 801-808, August 1985.

Substitution of lost packets is generally not appropriate for use in TDMA systems that do not use circular interleaving and therefore exhibit excessive lost packet path lengths. Other techniques that can be used to improve speech retrieval include, for example, interpolation and prediction.

ES 2 313 717 T3

Another technique that can be used to further reduce the maximum lost packet path lengths involves fast voice activity detection (FSAD). FSAD exploits the fact that gaps of silence generally exist during a given conversation state. The present invention may utilize FSAD to further increase the capacity of the TDD or STDD system beyond what can be achieved with conventional slow speech activity detection (SAD) techniques. The six-state Markov model 700 shown in Fig. 7 can be modified to consider FSAD by partitioning each talk state of the model 700 into sub-states. A user can be characterized by moving through these sub-states while the user is within the corresponding conversation state. FSAD involves partitioning at least two distinct groups of states in the 700 model into sub-states. The first group includes the TS and ST states and the second group includes the TT1 and TT2 states. Additional details regarding FSAD can be found in, for example, DJ Goodman and SX Wei, "Multiple Access Efficiency by Packet Reservation," IEEE Trans. Veh. Tech., Vol. 40, No. 1, pp. 170-176, February 1991.

Figs. 10A and 10B illustrate an exemplary partition of the first and second groups, respectively, into sub-states. Sub-states are identified as either mini-conversation (MT) or mini-silence (MS) states within a user's particular conversation state. Fig. 10A indicates that a TS state can be divided into two states MT-S and MS-S, in which the first user is in an MT or MS state while the other user is silent. The TS state can exit both the MT-S state and the MS-S state and when the user is in the TS state the conversation can be characterized as being in the MT-S or MS-S state. A similar division between sub-states is used for the ST state. Fig. 10B indicates that a TT state in which both users are conversing at the same time can be divided into four different sub-states designated MT-MS, MT-MT, MS-MS, and MS-MT. This division is used for both states TT1 and TT2 of the model Fig. 7. The division into sub-states in this example thus produces a total of 14 sub-states that can be written as follows: {1_TO, 1b}, {2_to, 2_b, 2_c, 2_d}, {3_to, 3_b, 3_c,3_d}, {4}, {5}, {6_TO, 6_b}. The numbers 1 to 6 correspond to the six states shown in Fig. 7. The subscript A designates the sub-state MT-S in the states TS and ST of Fig. 7 and the sub-state MT-MT in the states TT1 and TT2. The subscripts B, C, and D designate the sub-states MS-MT, MT-MS, and MS-MS, respectively, in states TT1 and TT2. The two silent states SS1 and SS2 are not divided into sub-states. A stationary probability distribution can be developed by this FSAD model by estimating a probability for each of the 14 sub-states. The calculations involved in compiling such a distribution are well known from experience. ordinary in the art and therefore are not further described here.

Fig. 11 shows an exemplary model that can be used to estimate lost packet path length reduction produced using FSAD in an STDD system. The model in Fig. 11 indicates that a user in a given mini-talk state MT will eventually exit that state with the probability P₇₅ to enter a silent state S or a mini-silence state MS. This simplified model is illustrative of the path lengths that will be observed in a real FSAD system since jumps from a mini-talk state to a mini-silence state generally occur much more frequently than jumps from one main state to another. . A conditional lost packet path length distribution can also be obtained in this case. The selected value of P₇₅ it can be the minimum within all the probabilities of transition of a step from a mini-talk state to any silence or mini-silence state, determined according to the stationary probability distribution noted above. This results in a jump greater than the actual cumulative distribution for the path lengths of the lost packets. Using this model the expected value of L for a user entering the blocked queue in the first position, for a system with 40 information slots and a frame duration of 2 ms, is on the order of 12 ms for a TDD system and around 7 ms for an STDD system. The details of the computation will be apparent to those skilled in the art and are therefore omitted. In this example, STDD is thus superior to TDD in strength relative to the path length of lost packets for a given loss rate when FS AD is used .

An important feature of FSAD in the present invention is that FSAD randomly spreads lost packets among users. As noted above, each user generally switches between an MT state and an MS very frequently within a given conversation state. FSAD therefore effectively performs additional randomization of user slots which further decreases the path length of lost packets. It should be noted that even in an FSAD system there is still the possibility that a path length experienced by a particular user can be made arbitrarily long. It is therefore preferable to use the circular interlacing of the present invention in conjunction with FSAD. The decision to use the circular interleaving of the present invention with or without the FSAD may involve a trade-off between the minimized path length and the increased complexity of system processing which generally accompanies the use of the FSAD. Of course, other types of voice activity detection could also be used, including techniques that operate at any appropriate detection speed.

FIG. 12 shows an exemplary communication system 1200. System 1200 includes a voice coder 1204 which processes a baseband input from, for example, a public telephone line connected to a base station in a cellular system. The coded voice is applied to a channel encoder 1208. The output of the channel encoder represents information packets to be transmitted to users from the base station. A channel interleaver device 1212 randomly interleaves the packets in a manner well known in the art to mitigate the effects of, for example, channel fading. It should be noted that channel interleaving, unlike the circular interlacing of the present invention described above, generally does not reduce the path lengths of lost packets. As will be described below, the circular interlacing is

ES 2 313 717 T3 performed in this embodiment using a processor 1244 that includes memory storage locations and implements queues such as those described in conjunction with Figs. 8A, 8B, 9A and 9B. Circular interleaving can use control information to identify users, and is appropriate for use in systems with K> 1 control information duty cycles. Those skilled in the art can easily determine the appropriate settings in the arrangement and / or processing of control information for systems in which K> 1.

Packets are modulated on one or more carrier signals in modulator 1214 and supplied to RF processor 1220 and antenna 1224. Antenna 1224 may be an omnidirectional antenna suitable for communicating with a number of different mobile users in a particular cell of a cellular system. System 1200 also receives signals from users through antenna 1224 and an RF processor 1220. The received signals are demodulated in a demodulator 1228. The demodulated packets are then processed in a channel de-interleaver device 1232 so that the previously applied channel interleaver device is removed and the positioning of a packet in a given time frame is compatible with the decoding applied by a channel decoder 1236. . A voice decoder 1240 converts the received information into a baseband output that can be delivered to a telephone line on the public telephone network. A processor 1244 directs the operation of, for example, elements 1204-1214 and 1228-1240 or subsets thereof, and in other embodiments one or more of these elements may be partially or fully incorporated within processor 1244. Processor 1244 can be implemented as a computer, microprocessor, application specific integrated circuit (ASIC), or any other appropriate firmware, software, hardware, or arrangement. In one embodiment, processor 1244 includes memory with a number of appropriate storage locations for storing, for example, user identifiers. Processor 1244 then provides circular interleaving using memory to implement one or more queues in the manner described above in conjunction with Figs. 8A, 8B, 9A and 9B. Processor 1244 controls the scrolling or other movement of user identifiers within queues such that users locked in one frame are provided with priority in the allocation of slots in a subsequent frame. In other embodiments, the processor could interact with an external memory unit to control circular interleaving. Processor 1244 can also be used to implement the above-described FSAD technique by detecting the MS and MT sub-states in voice signals and then organizing and distributing packets accordingly. Details regarding the implementation of FSAD in a circular system are generally well known in the art and will therefore not be further described here.

Although the system 1200 is illustrated processing baseband voice signals and using interleaving and channel coding, it must be emphasized that this is not done by way of limitation. For example, the present invention is suitable for use in systems that communicate any type of data and in systems that do not use interleaving and / or channel coding. Interleaving / deinterlacing and channel encoding / decoding generally randomizes a communication channel and thus mitigates the effects of, for example, channel fading. However, this is usually at the expense of the increased total delay. A preferred embodiment of the invention therefore eliminates channel interleaving and channel coding and uses any of a number of well-known space diversity techniques to control channel fading.

Fig. 13 is a flow chart illustrating circular entanglement.

Decision step 1302 indicates that when a given user enters an active state, for example by initiating a conversation, a queue position is assigned to that user in step 1306. A user identifier corresponding to that user is then stored in a queue at step 1308. In this embodiment, the circular interleaving device was assumed to include an uplink tail and a downlink tail, each with a distributed slot portion and a waiting portion, as described in conjunction with Figs. 9A and 9B above. A reference to a tail in conjunction with Fig. 13 it must therefore be understood as referring to the uplink or downlink queue, depending on whether the given user is communicating on an uplink or a downlink.

In decision step 1312, an attempt is made to allocate a timeslot in the current frame to the user. If the slot is distributed in step 1312, communication with the user can take place in the distributed slot as shown in step 1316. Decision step 1322 indicates that if the same user does not remain active during the next frame, any previously allocated slots are returned to a repository of unused slots as shown in step 1324. The process then returns to step 1302 and is it stays there until the inactive user re-enters an active state. If the user remains active in step 1322, the position of the queue assigned to the user is updated based on the circular interleaving described above as shown in step 1328. For example, we assume that user A in Fig. 8A is the time slot of the first frame was distributed, corresponding to a first tail position in frame n-1. During a subsequent frame n, user A is assigned a different queue position, such as the queue position that corresponds to the end of the locked queue 820 in FIG. 8B. Step 1330 indicates that the updated queue position for the user is stored in the form of a user identifier. The process then returns to step 1312 to attempt to allocate a slot in the next frame for that user. The steps shown are repeated by multiple users in each frame, and from frame to frame, according to the circular interlacing described above. The queue can be held in, for example, processor 1244 of FIG. 12, and can be implemented in random access memory, cache memory, or other types of electronic or magnetic memory. The steps shown in Fig. 13 provide circular interlacing, for example, keeping track of which slots have been previously distributed to users and shifting

ES 2 313 717 T3 or otherwise altering the slots distributed to any of these users who remain active in the next frame.

As previously described in conjunction with Figs. 8A, 8B, 9A and 9B, a user who is assigned a slot in a first slot position in the current frame can be moved out of that position and placed at the end of a blocked queue, or in a waiting portion of an uplink or downlink queue, during a subsequent frame. This can occur if, for example, there are other user identifiers stored in the locked queue or the waiting portion of a queue, all available slots in the subsequent frame are distributed to other users, and the user who was previously assigned the first slot position remains active. Of course, there are many variations on this technique that could be used. In general, interleaving techniques can be described as providing a slot distribution priority to a previously blocked user. Circular interlacing is only one possible technique to provide priority. Other techniques include applying any of a number of alternative permutations to the order of the slot distribution so that the risk of lost packets is spread over a large number of users. Additional alternatives include applying circular interleaving to only a subset of the active users in a given frame, or allowing one or more users to maintain possession of a particular slot over a number of frames. It should be noted that it is not necessary to store an identifier that corresponds to a previously blocked user. For example, altering the slot assignments before or after distribution so that a user who was assigned the first slot position is not automatically assigned that same slot in a subsequent frame, but instead must compete with all the other users for another slot in the frame, a priority is in effect given to a previously blocked user.

The embodiments of the invention described above can also be used in a frequency division multiplexing (FDM) system. In such a system, a timeslot allocated to a user represents one of a number of available carrier frequencies. The term "frame slot" as used herein is therefore intended to include, for example, time slots and frequency slots. Circular interleaving or, more generally, slot distribution permutation of the present invention is then applied to the various FDM carrier frequencies, in a manner similar to that described above. A user who is locked in one frame, and therefore a carrier frequency is not distributed to him, receives a priority in the distribution in the subsequent frame. The present invention can also be implemented in a code division system. Those skilled in the art can easily adapt the teachings herein to implement a wide variety of different time division, frequency division, and code division systems.

Although the foregoing description illustrates the utility of the present invention primarily in terms of a wireless communication system incorporating an STDD multiple access technique, it will be understood that the apparatus and methods of the present invention are generally appropriate for use with other TDMA communication techniques, including TDD / SAD. Many variations can be made on the embodiments shown, including the placement and implementation of the circular interlacing device in relation to other elements of the system, the type of interlacing device used, and the way the interlacing alters the slot distribution to provide a priority to a previously blocked user. These and other alternatives and variations on the arrangements shown will be readily apparent to those skilled in the art.