Page 111 - DCAP406_DCAP_207_Computer Networks

Computer Networks/Networks

Notes sender for retransmission of the data, a back-channel is not required in forward error correction,
and it is therefore suitable for simplex communication such as broadcasting. Error-correcting
codes are frequently used in lower-layer communication, as well as for reliable storage in
media such as cds, dvds, hard disks, and ram.
Error-correcting codes are usually distinguished between convolution codes and block codes:

Convolution codes are processed on a bit-by-bit basis. They are particularly suitable for
implementation in hardware, and the viterbi decoder allows optimal decoding.

Block codes are processed on a block-by-block basis. Early examples of block codes are
repetition codes, hamming codes and multidimensional parity-check codes. They were
followed by a number of efficient codes, reed-solomon codes being the most notable due
to their current widespread use. Turbo codes and low-density parity-check codes (ldpc)
are relatively new constructions that can provide almost optimal efficiency.

Shannon’s theorem is an important theorem in forward error correction, and describes the
maximum information rate at which reliable communication is possible over a channel that has
a certain error probability or signal-to-noise ratio (snr). This strict upper limit is expressed in
terms of the channel capacity. More specifically, the theorem says that there exist codes such that
with increasing encoding length the probability of error on a discrete memory less channel can
be made arbitrarily small, provided that the code rate is smaller than the channel capacity. The
code rate is defined as the fraction k/n of k source symbols and n encoded symbols.
The actual maximum code rate allowed depends on the error-correcting code used, and may be
lower. This is because Shannon’s proof was only of existential nature, and did not show how to
construct codes which are both optimal and have efficient encoding and decoding algorithms.

Self Assessment

State whether the following statements are true or false:
5. Shannon’s theorem is an important theorem in forward error correction.

6. The actual maximum code rate allowed depends on the error-correcting code used.
7. The code rate is defined as the fraction k/n of k source symbols and n encoded symbols.
8. Block codes are processed on a bit-by-bit basis.
9. Early examples of block codes are repetition codes, hamming codes and multidimensional
parity-check codes.
10. Turbo codes and low-density parity-check codes (ldpc) are relatively new constructions
that can provide almost optimal efficiency.
7.3 Summary

Data link layer describes the techniques to access a shared communication channel and
reliable data transmission. Its main tasks are framing, checksums, error detection and
correction, acknowledgement, flow control, encapsulating packets from network layer to
frames, etc.

The data link layer provides unacknowledged connectionless service, acknowledged
connectionless service and acknowledged connection-oriented service.
Parity check is the simplest form of error detection method as the receiver needs to count
only the number of 1’s in the received data stream with additional parity bit.

104 LOVELY PROFESSIONAL UNIVERSITY