[go: up one dir, main page]

FR2751105A1 - Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante - Google Patents

Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante Download PDF

Info

Publication number
FR2751105A1
FR2751105A1 FR9608735A FR9608735A FR2751105A1 FR 2751105 A1 FR2751105 A1 FR 2751105A1 FR 9608735 A FR9608735 A FR 9608735A FR 9608735 A FR9608735 A FR 9608735A FR 2751105 A1 FR2751105 A1 FR 2751105A1
Authority
FR
France
Prior art keywords
operator
shift
sequence
floating point
shift operator
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
FR9608735A
Other languages
English (en)
Other versions
FR2751105B1 (fr
Inventor
Marc Bavant
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Thales SA
Original Assignee
Thomson CSF SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Thomson CSF SA filed Critical Thomson CSF SA
Priority to FR9608735A priority Critical patent/FR2751105B1/fr
Priority to EP97933718A priority patent/EP0910926A1/fr
Priority to US09/147,512 priority patent/US6144978A/en
Priority to CA002260084A priority patent/CA2260084A1/fr
Priority to PCT/FR1997/001286 priority patent/WO1998003034A1/fr
Publication of FR2751105A1 publication Critical patent/FR2751105A1/fr
Application granted granted Critical
Publication of FR2751105B1 publication Critical patent/FR2751105B1/fr
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00Data switching networks
    • H04L12/54Store-and-forward switching systems 
    • H04L12/56Packet switching systems
    • H04L12/5601Transfer mode dependent, e.g. ATM
    • H04L12/5602Bandwidth control in ATM Networks, e.g. leaky bucket
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04QSELECTING
    • H04Q11/00Selecting arrangements for multiplex systems
    • H04Q11/04Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0428Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
    • H04Q11/0478Provisions for broadband connections
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00Data switching networks
    • H04L12/54Store-and-forward switching systems 
    • H04L12/56Packet switching systems
    • H04L12/5601Transfer mode dependent, e.g. ATM
    • H04L2012/5625Operations, administration and maintenance [OAM]
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00Data switching networks
    • H04L12/54Store-and-forward switching systems 
    • H04L12/56Packet switching systems
    • H04L12/5601Transfer mode dependent, e.g. ATM
    • H04L2012/5629Admission control
    • H04L2012/5631Resource management and allocation
    • H04L2012/5632Bandwidth allocation
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00Data switching networks
    • H04L12/54Store-and-forward switching systems 
    • H04L12/56Packet switching systems
    • H04L12/5601Transfer mode dependent, e.g. ATM
    • H04L2012/5638Services, e.g. multimedia, GOS, QOS
    • H04L2012/5646Cell characteristics, e.g. loss, delay, jitter, sequence integrity
    • H04L2012/5652Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

Le procédé s'applique au calcul approché de la moyenne exponentielle d'une suite de nombres un codés dans un format à virgule flottante utilisé pour convoyer certaines informations de débit dans des réseaux ATM, chaque nombre étant défini à l'aide d'un exposant en et d'une mantisse mn par une relation de la forme un = 2**en . (1 + mn /512). Il consiste à approximer la moyenne exponentielle par la valeur du code associée à la moyenne exponentielle des mots-code Un = 512.en + mn . Application: commutateurs ATM, terminaux ATM.

Description

La présente invention concerne un procédé de calcul approché de la moyenne exponentielle d'une suite de nombres codés dans le format à virgule flottante utilisé pour convoyer certaines informations de débit dans des réseaux de transmissions de données par paquets connus sous l'abréviation anglo-saxonne ATM de "asynchronous fransfer mode".
Les réseaux ATM fournissent plusieurs catégories de service de transmission de données, dont un dénommé sous l'abréviation anglo-saxonne ABR "available bit rate". Ce dernier service permet à l'usager d'utiliser la bande passante disponible sur le trajet d'une connexion préalablement établie sans l'obliger à une réservation statique de ressources lors de l'établissement de la connexion. En contrepartie de cette souplesse, les deux extrémités de la connexion doivent adapter leur débit à la bande passante disponible. À cet effet, des cellules ATM particulières, dénommées cellules RM, où RM est l'abréviation anglo-saxonne de "ressource management', permettent de renseigner les extrémités d'une connexion sur la disponibilité des ressources dans le réseau. Ces cellules, générées et traitées en temps réel par les équipements d'extrémité attachés au réseau, aussi bien que par les commutateurs ATM qui forment les noeuds du réseau, comportent des champs destinés à convoyer des informations de débit.
Ces champs représentent par exemple, le débit autorisé courant de la source -- qui est connue sous l'abréviation anglo-saxonne CCR "current cell rate" --, ou le débit conseillé par le réseau à la source -- qui est connu sous l'abréviation anglo-saxonne de ER "expllcit cell rate". Ces champs font l'objet d'un codage en virgule flottante particulier caractérisé par un bit de nullité, 5 bits d'exposant et 9 bits de mantisse.
Les commutateurs qui ont cette capacité calculent le débit ER et l'inscrivent dans les cellules RM. Parmi tous les algorithmes possibles pour réaliser ce calcul, une famille d'algorithmes met en oeuvre un calcul de la "moyenne exponentielle" des débits CCR convoyés par les cellules RM. La "moyenne exponentielle" n'est rien d'autre que le résultat d'un filtrage linéaire obtenu à la sortie d'un filtre numérique du premier ordre à temps discret. En désignant par un la suite des valeurs qui sont appliquées au filtre et xn la suite des états du filtre, I'équation d'état du filtre s'écrit:
xn+l = a . xn + (1 - a) . un (1) où a est un paramètre inférieur à 1, proche de 1, qui définit l'horizon du filtre. La suite xn représente ainsi une sorte de moyenne instantanée à plus ou moins long terme des valeurs entrées un.
Le calcul de la "moyenne exponentielle" est une opération qui doit se faire très rapidement, typiquement pendant le temps de commutation d'un paquet ATM (cellule). A titre d'exemple, pour une artère de réseau à 155 Bits, le temps de commutation d'une cellule dans un commutateur relié à cette artère est de 2,8 microsecondes environ. Etant donnés le codage des données un en format flottant et la relative complexité de traitement de ces deux multiplications suivies d'une addition, il est presque indispensable de faire appel à un microprocesseur doté de la capacité d'effectuer des opérations arithmétiques dans ce type de codage en virgule flottante. Or ces processeurs ne sont pas pour l'heure très bon marché.
Le but de l'invention est de pallier les inconvénients précités.
A cet effet, I'invention a pour objet un procédé pour le calcul approché de la moyenne exponentielle d'une suite de nombre un codés dans un format à virgule flottante utilisé pour convoyer certaines informations de débit dans des réseaux ATM, chaque nombre étant défini à l'aide d'un exposant en et d'une mantisse mn par une relation de la forme un = 2en . (1 + mn/512), caractérisé en ce qu'il consiste à approximer la moyenne exponentielle par la valeur du code associée à la moyenne exponentielle des mots-code Un = 512.en + mn.
L'invention a également pour objet un dispositif pour la mise en oeuvre du procédé. Le procédé et le dispositif selon l'invention ont pour principal avantage qu'ils permettent d'obtenir rapidement une valeur approchée de la moyenne exponentielle par manipulation directe des mots-code, en arithmétique entière et sans passage par le format à virgule fixe, ce qui met le calcul à la portée des microprocesseurs courants.
D'autres caractéristiques et avantages de l'invention apparaîtront dans la description qui suit faite en regard des figures des dessins annexés qui représentent:
- La figure 1, un dispositif pour la mise en oeuvre du procédé selon l'invention.
- Les figures 2a à 2c des courbes pour illustrer le processus de filtrage mis en oeuvre par l'invention.
Le code utilisé pour coder l'information de débit dans une cellule RM d'un réseau ATM est un codage à virgule flottante suivant la relation:
Un = 2en (1 + mn/512) (2) où l'exposant en est un nombre entier codé sur 5 bits, compris entre 0 et 31, et mn, la mantisse, est un nombre entier codé sur 9 bits, compris entre 0 et 511. A chaque valeur du code un est associé un mot code Un comportant quatorze bits significatifs, défini par la relation
Un = 512 - en + mn (3) en faisant volontairement abstraction du fait que le codage défini par les instances de normalisation prévoit l'utilisation d'un bit supplémentaire comme indication de la valeur 0, comme cette valeur doit touiours être traitée à part, il est suggéré de remplacer les valeurs 0 par les valeurs
Figure img00030001
Le procédé selon l'invention consiste à remplacer dans la relation (1) qui définit l'équation d'un filtre du premier ordre, la suite des valeurs d'entrée un par la suite des mots-code Un. Les valeurs obtenues pour Xn sont alors des mots-codes associés à des valeurs très proches de la moyenne exponentielle et conviennent alors parfaitement pour le calcul des débits ER. Cette simplification élimine le besoin de décoder les mots de code.
En choisissant correctement la valeur de a il est aussi possible de limiter les opérations de multiplication.
Par exemple, si a est égal à 15/16, l'équation d'état du filtre devient
Xn+1 = (5.Xn+Un)/16. (4)
Ce qui s'écrit encore suivant la relation:
Xn+1 = ((Xn 4)-Xn+Un) 4 (5) où les signes < < et > > désignent comme en langage C des opérateurs de décalage binaire à gauche ou à droite. Des résultats comparables peuvent aussi être obtenus avec d'autres valeurs remarquables de a, telles que par exemple (2r- 2s)i2r.
Un dispositif correspondant pour la mise en oeuvre du procédé selon l'invention est montré à la figure 1. Celui-ci comprend, un opérateur d'addition 1 recevant sur une première entrée d'opérande les mots-code Un et sur une deuxième entrée d'opérande la sortie d'un opérateur soustracteur 2. Il comprend également un premier opérateur de décalage 3 qui est couplé en sortie de l'opérateur additionneur 1 pour fournir la suite de mots-code Xn. La sortie du premier opérateur de décalage 3 est couplée à une première entrée d'opérande marquée "+" de l'opérateur soustracteur 2 par l'intermédiaire d'un deuxième opérateur de décalage 4 et d'un circuit de retard 5 reliés en série. Un quatrième opérateur de décalage 6 assure la transmission des motscode Un sur la première entrée d'opérande de l'opérateur d'addition 1.
La deuxième entrée d'opérande marquée "-" de l'opérateur soustracteur 2 est couplée à la sortie du circuit de retard 5 par l'intermédiaire d'un troisième opérateur de décalage. Suivant ce mode de réalisation, le premier opérateur de décalage 3 effectue un décalage de r bits vers la droite, le deuxième opérateur de décalage 4 effectue un décalage de r bits vers la gauche, le troisième opérateur 6 et le quatrième opérateur de décalage 7 effectuent un décalage de s bits vers la gauche. L'équation d'état du filtre est alors de la forme:
Xns1 = ((2r-2S)Xn + 2sUn)/2r (6)
Une comparaison des résultats obtenus par le procédé de calcul approché d'une moyenne exponentielle selon l'invention avec la méthode de calcul non approché est représentée à la figure 2b, pour une suite des valeurs du code un représentée figure 2a et obtenue en superposant une oscillation harmonique basse fréquence, une oscillation harmonique de plus haute fréquence et une composante aléatoire. Sur la figure 2b, xn représente la moyenne exponentielle exacte obtenue et F(Xn) est la moyenne exponentielle approchée obtenue en appliquant la relation (5), F étant la fonction qui associe une valeur du code à un mot-code.
La figure 2c, fait apparaître les différences entre les deux courbes de la figure 2b en donnant une représentation de l'erreur relative qui est commise en remplaçant xn par F(Xn). II est à noter que cette erreur est plus élevée pour les faibles valeurs de xn.

Claims (5)

REVENDICATIONS
1. Procédé pour le calcul approché de la moyenne exponentielle d'une suite de nombre un codés dans un format à virgule flottante utilisé pour convoyer certaines informations de débit dans des réseaux ATM, chaque nombre étant défini à l'aide d'un exposant en et d'une mantisse mn par un relation de la forme un = 2en . (1 + mn/512), caractérisé en ce qu'il consiste à approximer la moyenne exponentielle par la valeur du code associée à la moyenne exponentielle des mots code Un = 512.en + mn.
2. Procédé selon la revendication 1, caractérisé en ce qu'il consiste à effectuer l'approximation de la suite des mots-code de la moyenne exponentielle des un par une relation de la forme: Xn+I = ((2r-2S).Xn+2sUn)l2r-
3. Procédé selon la revendication 2, caractérisé en ce que r = 4 et s = 0.
4. Dispositif pour la mise en oeuvre du procédé selon l'une quelconque des revendication 1 à 3, caractérisé en ce qu'il comprend
- un opérateur d'addition (1) recevant sur une première entrée d'opérande le mot de code Un et qui est couplé par une deuxième entrée d'opérande à la sortie d'un opérateur soustracteur (2),
- un premier opérateur de décalage (2) qui est couplé en sortie de l'opérateur additionneur (1) pour fournir la suite des codes Xn
- un deuxième opérateur de décalage (4) couplé en série avec un circuit de retard de 1 bit (5) entre la sortie du premier opérateur de décalage fournissant la suite des codes Xn et une entrée de l'opérateur soustracteur (2)
- un troisième opérateur de décalage (6) couplé entre la sortie du circuit de retard d'un bit (5) et une deuxième entrée d'opérande de l'opérateur soustracteur (2)
- et un quatrième opérateur de décalage (7) pour appliquer le mot de code Un sur la première entrée d'opérande de l'opérateur d'addition (1).
5. Dispositif selon la revendication 4, caractérisé en ce que le premier opérateur de décalage (3) effectue un décalage de r bits vers la droite, le deuxième opérateur de décalage (4) effectue un décalage de r bits vers la gauche le troisième opérateur de décalage (6) et la quatrième opérateur de décalage (7) effectuent un décalage de s bits vers la gauche.
FR9608735A 1996-07-12 1996-07-12 Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante Expired - Fee Related FR2751105B1 (fr)

Priority Applications (5)

Application Number Priority Date Filing Date Title
FR9608735A FR2751105B1 (fr) 1996-07-12 1996-07-12 Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante
EP97933718A EP0910926A1 (fr) 1996-07-12 1997-07-11 Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante
US09/147,512 US6144978A (en) 1996-07-12 1997-07-11 Method and device for the approximative computation of the exponential mean of a sequence of coded numbers in floating point format
CA002260084A CA2260084A1 (fr) 1996-07-12 1997-07-11 Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante
PCT/FR1997/001286 WO1998003034A1 (fr) 1996-07-12 1997-07-11 Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
FR9608735A FR2751105B1 (fr) 1996-07-12 1996-07-12 Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante

Publications (2)

Publication Number Publication Date
FR2751105A1 true FR2751105A1 (fr) 1998-01-16
FR2751105B1 FR2751105B1 (fr) 1998-12-18

Family

ID=9493990

Family Applications (1)

Application Number Title Priority Date Filing Date
FR9608735A Expired - Fee Related FR2751105B1 (fr) 1996-07-12 1996-07-12 Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante

Country Status (5)

Country Link
US (1) US6144978A (fr)
EP (1) EP0910926A1 (fr)
CA (1) CA2260084A1 (fr)
FR (1) FR2751105B1 (fr)
WO (1) WO1998003034A1 (fr)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2751108B1 (fr) * 1996-07-12 1998-10-30 Thomson Csf Procede et dispositif de mesure de la proportion de cellules atm satisfaisant a un critere determine en un point quelconque d'un flot de cellules atm
FR2751160B1 (fr) 1996-07-12 1998-10-30 Thomson Csf Procede de detection de congestion amont au sein d'un commutateur atm a architecture repartie et memorisation en entree
FR2770070B1 (fr) 1997-10-20 2000-02-04 Thomson Csf Procede de controle de flux au sein d'un commutateur atm a architecture repartie
FR2811179B1 (fr) * 2000-06-30 2002-09-27 Thomson Csf Procede de routage de trame ip entre les usagers d'un reseau a graphe variable
US6741565B1 (en) 2000-07-06 2004-05-25 Telefonaktiebolaget Lm Ericsson (Publ) System and method for estimating cell rate in an ATM network

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4774685A (en) * 1985-01-31 1988-09-27 Analog Devices, Inc. Approximation system
US4815354A (en) * 1984-10-30 1989-03-28 Nippon Gakki Seizo Kabushiki Kaisha Tone signal generating apparatus having a low-pass filter for interpolating waveforms
US5258938A (en) * 1990-11-30 1993-11-02 Norio Akamatsu Interpolating method using bit-shift and addition/subtraction operations

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3619586A (en) * 1968-11-25 1971-11-09 Research Corp Universal digital filter for linear discrete systems
US5824936A (en) * 1997-01-17 1998-10-20 Crystal Semiconductor Corporation Apparatus and method for approximating an exponential decay in a sound synthesizer

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4815354A (en) * 1984-10-30 1989-03-28 Nippon Gakki Seizo Kabushiki Kaisha Tone signal generating apparatus having a low-pass filter for interpolating waveforms
US4774685A (en) * 1985-01-31 1988-09-27 Analog Devices, Inc. Approximation system
US5258938A (en) * 1990-11-30 1993-11-02 Norio Akamatsu Interpolating method using bit-shift and addition/subtraction operations

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
KAI-YEUNG SIU ET AL: "INTELLIGENT CONGESTION CONTROL FOR ABR SERVICE IN ATM NETWORKS", COMPUTER COMMUNICATIONS REVIEW, vol. 24, no. 5, 1 October 1994 (1994-10-01), pages 81 - 106, XP000501061 *
PRYCKER, MARTIN DE: "Asynchronous transfer mode : solution for broadband ISDN", 1995, PRENTICE HALL INTERNALIONAL (UK) LIMITED, GREAT BRITAIN, XP002028512 *

Also Published As

Publication number Publication date
FR2751105B1 (fr) 1998-12-18
CA2260084A1 (fr) 1998-01-22
EP0910926A1 (fr) 1999-04-28
US6144978A (en) 2000-11-07
WO1998003034A1 (fr) 1998-01-22

Similar Documents

Publication Publication Date Title
EP0493286B1 (fr) Système de transmission par paquets à compression de données, procédé et équipement correspondant
EP0321318B1 (fr) Procédé et dispositif de codage et de décodage pour la transmission d&#39;images à travers un réseau à débit variable
FR2880482A1 (fr) Dispositif de conversion d&#39;un signal transmis en un signal numerique
FR2751105A1 (fr) Procede et dispositif de calcul approche de la moyenne exponentielle d&#39;une suite de nombres codes dans le format a virgule flottante
EP0246701A1 (fr) Dispositif de codage à modulation différentielle par impulsions codées et dispositif de décodage associé
WO2002007324A1 (fr) Dispositif d&#39;emission/reception de donnees numeriques capable de traiter des debits differents, en particulier dans un environnement vdsl
EP0771132B1 (fr) Dispositif de régulation du flux de cellules ATM au sein d&#39;un brasseur ATM
EP0334714B1 (fr) Codeur différentiel à filtre prédicteur auto adaptatif et décodeur utilisable en liaison avec un tel codeur
Leung-Yan-Cheong MULTI-USER AND WIRETAPE CHANNELS INCLUDING FEEDBACK.
EP0030194B1 (fr) Etage prédicteur pour système de compression de débit numérique
EP0098198A2 (fr) Procédé et système de compression de débit de données transmises entre au moins un émetteur et un récepteur d&#39;images de télévision
EP0690584A1 (fr) Circuit de localisation d&#39;erreurs d&#39;un décodeur Reed-Solomon
FR2494529A1 (fr) Systeme de transmission numerique a codage adaptatif d&#39;informations analogiques echantillonnees et transformees par transformation orthogonale
FR2747489A1 (fr) Procede et dispositif pour le calcul approche dans des reseaux atm du produit de mots de code d&#39;information codes dans un format a virgule flottante
EP0288353A1 (fr) Procédé de commutation de signaux numériques asynchrones, et dispositif pour la mise en oeuvre de ce procédé
EP0982866B1 (fr) Procédé de codage convolutif et de transmission par paquets d&#39;un flux série de données numériques, procédé et dispositif de décodage correspondants
EP0910911B1 (fr) Procede et dispositif de mesure de la proportion d&#39;un flot de cellules atm satisfaisant a un critere determine
FR2811169A1 (fr) Procede et dispositif de decodage et systemes les mettant en oeuvre
EP1044543A1 (fr) Modulation d&#39;un signal numerique a spectre etroit et a enveloppe sensiblement constante
FR2658676A1 (fr) Dispositif de quantification a debit de codage numerique variable.
Tan et al. Series representations for Rice's Ie function
EP0589768A1 (fr) Dispositif de filtrage pour égaliseur à estimation de séquence
EP0459927B1 (fr) Méthode de mesure de la charge d&#39;un multiplex et circuit pour sa mise en oeuvre
FR2503897A1 (fr) Procede et dispositif de calcul du logarithme du module d&#39;un signal video frequence a partir de ses composantes en quadrature, application a un dispositif de traitement d&#39;informations radar ou de telecommunications
FR2808951A1 (fr) Procede de modulation-demodulation a 4 etats de phase utilisant le poinconnage de certains symboles pour ameliorer l&#39;acquisition de la synchronisation phase- frequence a faible rapport signal a bruit

Legal Events

Date Code Title Description
CD Change of name or company name
ST Notification of lapse