Lecture 6 - Notes

January 21, 2016

  • Speed: Bits per second
  • Delay: Milliseconds
    • Transmission Delay: $\frac{\text{Packet Length}}{\text{Link Speed}}$
    • Propagation Delay: $\frac{\text{Travel Distance}}{\text{Signal Speed}}$
    • Processing Delay: Magic
    • Queueing Delay: Complicated
  • Loss: Percentage
    • Transmission Error
    • Network Congestion
  • Service Provided by the Physical Layer
    • Bit delivery
  • Service Provided to the Network Layer
    • Frame delivery
    • Error control
    • Flow control
    • Medium Access
Layer Units
Network Packet
Link Frame
Physical Bits

Packet Framing

Wikipedia

definition: Networks use Packet Framing to format data during transmission. It can be thought of as the envelope for a letter and contains addressing data as well as checksums for error checking.

Byte Stuffing

Wikipedia

definition: When transmitting data using packet framing the data portion must be delimited. It is ofter zero delimited. Byte Stuffing is a way we escape the zero's already inside the data.

With bit stuffing we can define a bit sequence as the escape sequence.

Error Control

How can we make sure the frames makes it to the other end correctly?

  • Frame Order: Added to the frames
  • Lost Frames: Wait for Timeout
  • Frame Correctness: Add check bits

Hamming Distance

We can create codewords,

These codewords can be generated a number of ways for checking the validity of data. A naive approach might be duplicating our data. For example if our data was $010$ then our check would also be $010$.

The Hamming Distance of codewords $a$ and $b$ is the number of pairwise different bits. This distance of a codeword set is the smallest hamming distance in the set. If our set has distance $d$ then we can detect $d-1$ bits of error and correct,

of error.

Example

If our generation scheme is to replicate the data once, like above, and we have two bits of data (for simplicity),

$0000$ $0101$ $1010$ $1111$
$0000$ N/A $d=2$ $d=2$ $d=4$
$0101$ $d=2$ N/A $d=4$ $d=2$
$1010$ $d=2$ $d=4$ N/A $d=2$
$1111$ $d=4$ $d=2$ $d=2$ N/A

we can see the codeword set has a hamming distance of $d = 2$ so we can detect $1$ bit of error and correct no bits.

Example

If our generation scheme is instead to replicate the data twice, and we still have two bits of data,

$000000$ $010101$ $101010$ $111111$
$000000$ N/A $d=3$ $d=3$ $d=6$
$010101$ $d=3$ N/A $d=6$ $d=3$
$101010$ $d=3$ $d=6$ N/A $d=3$
$111111$ $d=6$ $d=3$ $d=3$ N/A

we can see the codeword set has a hamming distance of $d = 3$ so we can detect $2$ bit of error and correct,

Multi Dimensional Parity Check Code

From Wikipedia

The two-dimensional parity-check code, usually called the optimal rectangular code, is the most popular form of multidimensional parity-check code.

Assume that the goal is to transmit the four-digit message "1234", using a two-dimensional parity scheme. First the digits of the message are arranged in a rectangular pattern:

Column 1 Column 2
Row 1 1 2
Row 2 3 4

Parity digits are then calculated by summing each column and row separately:

Column 1 Column 2 Parity
Row 1 1 2 3
Row 2 3 4 7
Parity 4 6

The eight-digit sequence "12334746" is the message that is actually transmitted. If any single error occurs during transmission then this error can not only be detected but can also be corrected as well. Let us suppose that the received message contained an error in the first digit. The receiver rearranges the message into the grid:

Column 1 Column 2 Parity
Row 1 9 2 3
Row 2 3 4 7
Parity 4 6

The receiver can see that the first row and also the first column add up incorrectly. Using this knowledge and the assumption that only one error occurred, the receiver can correct the error. In order to handle two errors, a 4-dimensional scheme would be required, at the cost of more parity digits.