Exit Zen
105
../../principles/reliability.rst:389
English
Reliable data transfer on top of an imperfect link
0/500 · 50
106
../../principles/reliability.rst:391
English
The datalink layer must deal with the transmission errors. In practice, we mainly have to deal with two types of errors in the datalink layer :
0/1430 · 143
107
../../principles/reliability.rst:393
English
Frames can be corrupted by transmission errors
0/460 · 46
108
../../principles/reliability.rst:394
English
Frames can be lost or unexpected frames can appear
0/500 · 50
110
../../principles/reliability.rst:399
English
To deal with these types of imperfections, reliable protocols rely on different types of mechanisms. The first problem is transmission errors. Data transmission on a physical link can be affected by the following errors :
0/2210 · 221
111
../../principles/reliability.rst:401
English
random isolated errors where the value of a single bit has been modified due to a transmission error
0/1000 · 100
112
../../principles/reliability.rst:402
English
random burst errors where the values of `n` consecutive bits have been changed due to transmission errors
0/1050 · 105
113
../../principles/reliability.rst:403
English
random bit creations and random bit removals where bits have been added or removed due to transmission errors
0/1090 · 109
114
../../principles/reliability.rst:405
English
The only solution to protect against transmission errors is to add redundancy to the frames that are sent. `Information Theory` defines two mechanisms that can be used to transmit information over a transmission channel affected by random errors. These two mechanisms add redundancy to the transmitted information, to allow the receiver to detect or sometimes even correct transmission errors. A detailed discussion of these mechanisms is outside the scope of this chapter, but it is useful to consider a simple mechanism to understand its operation and its limitations.
0/5700 · 570
115
../../principles/reliability.rst:407
English
`Information theory` defines `coding schemes`. There are different types of coding schemes, but let us focus on coding schemes that operate on binary strings. A coding scheme is a function that maps information encoded as a string of `m` bits into a string of `n` bits. The simplest coding scheme is the (even) parity coding. This coding scheme takes an `m` bits source string and produces an `m+1` bits coded string where the first `m` bits of the coded string are the bits of the source string and the last bit of the coded string is chosen such that the coded string will always contain an even number of bits set to `1`. For example :
0/6380 · 638
116
../../principles/reliability.rst:409
English
`1001` is encoded as `10010`
0/280 · 28
117
../../principles/reliability.rst:410
English
`1101` is encoded as `11011`
0/280 · 28
118
../../principles/reliability.rst:412
English
This parity scheme has been used in some RAMs as well as to encode characters sent over a serial line. It is easy to show that this coding scheme allows the receiver to detect a single transmission error, but it cannot correct it. However, if two or more bits are in error, the receiver may not always be able to detect the error.
0/3300 · 330
119
../../principles/reliability.rst:414
English
Some coding schemes allow the receiver to correct some transmission errors. For example, consider the coding scheme that encodes each source bit as follows :
0/1570 · 157
120
../../principles/reliability.rst:416
English
`1` is encoded as `111`
0/230 · 23
121
../../principles/reliability.rst:417
English
`0` is encoded as `000`
0/230 · 23
122
../../principles/reliability.rst:419
English
For example, consider a sender that sends `111`. If there is one bit in error, the receiver could receive `011` or `101` or `110`. In these three cases, the receiver will decode the received bit pattern as a `1` since it contains a majority of bits set to `1`. If there are two bits in error, the receiver will not be able anymore to recover from the transmission error.
0/3700 · 370
125
../../principles/reliability.rst:426
English
To understand `error detection codes`, let us consider two devices that exchange bit strings containing `N` bits. To allow the receiver to detect a transmission error, the sender converts each string of `N` bits into a string of `N+r` bits. Usually, the `r` redundant bits are added at the beginning or the end of the transmitted bit string, but some techniques interleave redundant bits with the original bits. An `error detection code` can be defined as a function that computes the `r` redundant bits corresponding to each string of `N` bits. The simplest error detection code is the parity bit. There are two types of parity schemes : even and odd parity. With the `even` (resp. `odd`) parity scheme, the redundant bit is chosen so that an even (resp. odd) number of bits are set to `1` in the transmitted bit string of `N+r` bits. The receiver can easily recompute the parity of each received bit string and discard the strings with an invalid parity. The parity scheme is often used when 7-bit characters are exchanged. In this case, the eighth bit is often a parity bit. The table below shows the parity bits that are computed for bit strings containing three bits.
0/11720 · 1172
126
../../principles/reliability.rst:429
English
3 bits string
0/130 · 13
127
../../principles/reliability.rst:429
English
Odd parity
0/100 · 10