Translation

English
`Bit stuffing` reserves the `01111110` bit string as the frame boundary marker and ensures that there will never be six consecutive `1` symbols transmitted by the physical layer inside a frame. With bit stuffing, a frame is sent as follows. First, the sender transmits the marker, i.e. `01111110`. Then, it sends all the bits of the frame and inserts an additional bit set to `0` after each sequence of five consecutive `1` bits. This ensures that the sent frame never contains a sequence of six consecutive bits set to `1`. As a consequence, the marker pattern cannot appear inside the frame sent. The marker is also sent to mark the end of the frame. The receiver performs the opposite to decode a received frame. It first detects the beginning of the frame thanks to the `01111110` marker. Then, it processes the received bits and counts the number of consecutive bits set to `1`. If a `0` follows five consecutive bits set to `1`, this bit is removed since it was inserted by the sender. If a `1` follows five consecutive bits sets to `1`, it indicates a marker if it is followed by a bit set to `0`. The table below illustrates the application of bit stuffing to some frames.
0/11800 · 1180
English French Actions
Many other types of encodings have been defined to transmit information over an electrical cable. All physical layers are able to send and receive physical symbols that represent values `0` and `1`. However, for various reasons that are outside the scope of this chapter, several physical layers exchange other physical symbols as well. For example, the Manchester encoding used in several physical layers can send four different symbols. The Manchester encoding is a differential encoding scheme in which time is divided into fixed-length periods. Each period is divided in two halves and two different voltage levels can be applied. To send a symbol, the sender must set one of these two voltage levels during each half period. To send a `1` (resp. `0`), the sender must set a high (resp. low) voltage during the first half of the period and a low (resp. high) voltage during the second half. This encoding ensures that there will be a transition at the middle of each period and allows the receiver to synchronize its clock to the sender's clock. Apart from the encodings for `0` and `1`, the Manchester encoding also supports two additional symbols : `InvH` and `InvB` where the same voltage level is used for the two half periods. By definition, these two symbols cannot appear inside a frame which is only composed of `0` and `1`. Some technologies use these special symbols as markers for the beginning or end of frames. De nombreux autres types de codages ont été définis pour transmettre des informations sur un câble électrique. Toutes les couches physiques sont capables d'envoyer et de recevoir des symboles physiques qui représentent les valeurs `0` et `1`. Cependant, pour diverses raisons qui sortent du cadre de ce chapitre, plusieurs couches physiques échangent également d'autres symboles physiques. Par exemple, le codage Manchester utilisé dans plusieurs couches physiques peut envoyer quatre symboles différents. Le codage Manchester est un schéma de codage différentiel dans lequel le temps est divisé en périodes de longueur fixe. Chaque période est divisée en deux moitiés et deux niveaux de tension différents peuvent être appliqués. Pour envoyer un symbole, l'expéditeur doit définir l'un de ces deux niveaux de tension pendant chaque demi-période. Pour envoyer un `1` (resp. `0`), l'expéditeur doit définir une tension élevée (resp. faible) pendant la première moitié de la période et une tension faible (resp. élevée) pendant la seconde moitié. Ce codage garantit qu'il y aura une transition au milieu de chaque période et permet au récepteur de synchroniser son horloge avec celle de l'émetteur. Outre les codages pour `0` et `1`, le codage Manchester supporte également deux symboles supplémentaires : `InvH` et `InvB` où le même niveau de tension est utilisé pour les deux demi-périodes. Par définition, ces deux symboles ne peuvent pas apparaître à l'intérieur d'une trame qui n'est composée que de `0` et `1`. Certaines technologies utilisent ces symboles spéciaux comme marqueurs de début ou de fin de trame.
Manchester encoding Le codage Manchester
All the functions related to the physical transmission or information through a wire (or a wireless link) are usually known as the `physical layer`. The physical layer allows thus two or more entities that are directly attached to the same transmission medium to exchange bits. Being able to exchange bits is important as virtually any information can be encoded as a sequence of bits. Electrical engineers are used to processing streams of bits, but computer scientists usually prefer to deal with higher level concepts. A similar issue arises with file storage. Storage devices such as hard-disks also store streams of bits. There are hardware devices that process the bit stream produced by a hard-disk, but computer scientists have designed filesystems to allow applications to easily access such storage devices. These filesystems are typically divided into several layers as well. Hard-disks store sectors of 512 bytes or more. Unix filesystems group sectors in larger blocks that can contain data or `inodes` representing the structure of the filesystem. Finally, applications manipulate files and directories that are translated in blocks, sectors and eventually bits by the operating system. Toutes les fonctions liées à la transmission physique ou à l'information transmise à travers un câble (ou une connexion sans fil) sont regroupées sous l'appellation `couche physique`. La couche physique permet ainsi à deux entités ou plus qui sont directement reliées par un même moyen de transmission d'échanger des bits. Pouvoir échanger des bits est fondamental puisque pratiquement n'importe quelle information peut être encodée comme une séquence de bits. Les ingénieurs électriciens sont habitués à traiter des flux de bits mais les informaticiens préfèrent habituellement faire usage de concepts plus haut niveau. Un problème similaire se pose quant aux systèmes de fichiers. Les périphériques de stockage tels que les disques durs stockent également des flux de bits. Il y a des périphériques matériels qui traitent directement le flux de bit produit par le disque dur mais les informaticiens ont conçu des systèmes de fichiers destinés à permettre aux applications d'accéder facilement à ces périphériques de stockage. Ces systèmes de fichiers sont généralement également divisés en plusieurs couches. Les disques durs stockent des secteurs de 512 bytes ou plus. Les systèmes de fichiers Unix regroupent les secteurs par blocs plus larges pouvant contenir des données ou `inodes` représentant la structure du système de fichiers. Enfin, les applications manipulent des fichiers et répertoires qui sont traduits en blocs, secteurs et enfin en bits par le système d'exploitation.
Computer networks use a similar approach. Each layer provides a service that is built above the underlying layer and is closer to the needs of the applications. The datalink layer builds upon the service provided by the physical layer. We will see that it also contains several functions. Les réseaux informatiques utilisent une approche similaire. Chaque couche fournit un service construit sur la couche en-dessous et est plus proche des besoins des applications. La couche de liaison de données est construite à partir du service fourni par la couche physique. Nous allons voir qu'elle contient aussi plusieurs fonctions.
The datalink layer La couche de liaison de données
To enable the transmission/reception of frames, the first problem to be solved is how to encode a frame as a sequence of bits, so that the receiver can easily recover the received frame despite the limitations of the physical layer.
If the physical layer were perfect, the problem would be very simple. We would simply need to define how to encode each frame as a sequence of consecutive bits. The receiver would then easily be able to extract the frames from the received bits. Unfortunately, the imperfections of the physical layer make this framing problem slightly more complex. Several solutions have been proposed and are used in practice in different network technologies.
Framing
The `framing` problem can be defined as : "`How does a sender encode frames so that the receiver can efficiently extract them from the stream of bits that it receives from the physical layer`".
A first solution to this problem is to require the physical layer to remain idle for some time after the transmission of each frame. These idle periods can be detected by the receiver and serve as a marker to delineate frame boundaries. Unfortunately, this solution is not acceptable for two reasons. First, some physical layers cannot remain idle and always need to transmit bits. Second, inserting an idle period between frames decreases the maximum bit rate that can be achieved.
Bit rate and bandwidth
Bit rate and bandwidth are often used to characterize the transmission capacity of the physical service. The original definition of `bandwidth <https://www.merriam-webster.com/dictionary/bandwidth>`_, as listed in the `Webster dictionary <https://www.merriam-webster.com/dictionary>`_ is `a range of radio frequencies which is occupied by a modulated carrier wave, which is assigned to a service, or over which a device can operate`. This definition corresponds to the characteristics of a given transmission medium or receiver. For example, the human ear is able to decode sounds in roughly the 0-20 KHz frequency range. By extension, bandwidth is also used to represent the capacity of a communication system in bits per second. For example, a Gigabit Ethernet link is theoretically capable of transporting one billion bits per second.
Given that multi-symbol encodings cannot be used by all physical layers, a generic solution which can be used with any physical layer that is able to transmit and receive only bits `0` and `1` is required. This generic solution is called `stuffing` and two variants exist : `bit stuffing` and `character stuffing`. To enable a receiver to easily delineate the frame boundaries, these two techniques reserve special bit strings as frame boundary markers and encode the frames so that these special bit strings do not appear inside the frames.
`Bit stuffing` reserves the `01111110` bit string as the frame boundary marker and ensures that there will never be six consecutive `1` symbols transmitted by the physical layer inside a frame. With bit stuffing, a frame is sent as follows. First, the sender transmits the marker, i.e. `01111110`. Then, it sends all the bits of the frame and inserts an additional bit set to `0` after each sequence of five consecutive `1` bits. This ensures that the sent frame never contains a sequence of six consecutive bits set to `1`. As a consequence, the marker pattern cannot appear inside the frame sent. The marker is also sent to mark the end of the frame. The receiver performs the opposite to decode a received frame. It first detects the beginning of the frame thanks to the `01111110` marker. Then, it processes the received bits and counts the number of consecutive bits set to `1`. If a `0` follows five consecutive bits set to `1`, this bit is removed since it was inserted by the sender. If a `1` follows five consecutive bits sets to `1`, it indicates a marker if it is followed by a bit set to `0`. The table below illustrates the application of bit stuffing to some frames.
Original frame
Transmitted frame
0001001001001001001000011
01111110000100100100100100100001101111110
0110111111111111111110010
01111110011011111011111011111011001001111110
01111110
0111111001111101001111110
For example, consider the transmission of `0110111111111111111110010`. The sender will first send the `01111110` marker followed by `011011111`. After these five consecutive bits set to `1`, it inserts a bit set to `0` followed by `11111`. A new `0` is inserted, followed by `11111`. A new `0` is inserted followed by the end of the frame `110010` and the `01111110` marker.
`Bit stuffing` increases the number of bits required to transmit each frame. The worst case for bit stuffing is of course a long sequence of bits set to `1` inside the frame. If transmission errors occur, stuffed bits or markers can be in error. In these cases, the frame affected by the error and possibly the next frame will not be correctly decoded by the receiver, but it will be able to resynchronize itself at the next valid marker.
`Bit stuffing` can be easily implemented in hardware. However, implementing it in software is difficult given the complexity of performing bit manipulations in software. Software implementations prefer to process characters than bits, software-based datalink layers usually use `character stuffing`. This technique operates on frames that contain an integer number of characters. In computer networks, characters are usually encoded by relying on the :term:`ASCII` table. This table defines the encoding of various alphanumeric characters as a sequence of bits. :rfc:`20` provides the ASCII table that is used by many protocols on the Internet. For example, the table defines the following binary representations :
`A` : `1000011` b
`0` : `0110000` b
`z` : `1111010` b
`@` : `1000000` b

Loading…

No matching activity found.
Browse all component changes

Glossary

English French
No related strings found in the glossary.

String information

Source string location
../../principles/reliability.rst:217
String age
5 years ago
Source string age
5 years ago
Translation file
locale/fr/LC_MESSAGES/principles/reliability.po, string 52