View page as slide show

Communications software and architecture

Error control

Errors in communication channel

  • Broken link
  • Lost packets
  • Corrupted packets
    • switched bits in frame
    • additional bits in frame
    • duplicates

Error detection and correction

  • Error detection
    • How the receiver can realise that the received data is corrupted
  • Error correction
    • Codes that not only detect error but may also be able to recover from that.
  • Methods are used to find random errors, not changes made intentionally
    • Against malicious attackers, Message authentication codes and secure hashes should be used.
  • Automatic retransmissions and sequence numbering are the protocol level methods

Terms

  • Bit error ratio (rate) (BER)
    • Describes the average probability of error in communication channel
  • Hamming Distance
    • The smallest distance between two equal length codewords
    • e.g. Hamming distance between sent and received message is same as amount of bits that has flipped.
    • Hamming distance for Error detection code, is the smallest distance of two valid codes
      • In principle the bigger the distance the more bit errors it is possible to detect.
    • all errors smaller than d-1 can be detected (d being Hamming distance)

Error detection

  • Simple parity bit
    • One additional bit and end of packet indicates whether there is even (0) or odd (1) amount of 1 bits in message
    • Cannot detect even number changes in the message.
    • Hamming distance is 2
  • Checksums
    • Result of mathematical algorithm which get the content of message as input (usually several characters)
    • Several solutions exist (e.g. TCP checksum)

Cyclic Redundancy Check (CRC)

  • One of the most common error detecting code
    • Relies on modulo 2 arithmetic
    • Requires generator pattern (P) that is known by sender and receiver
      • can be defined in communication standard
      • e.g. IEEE link level protocols use 32 bit crc with generator 100000100110000010001110110110111
  • parts:
    • M = Frame to be sent (k-bits)
    • F = n-bit Frame check sequence
    • T = Message to be transmitted (k+n bits) M ||F
      • T = (2^n)*M + F
    • P = n+1 bit generator pattern
  • Goal is to get T so that T/P has no remainder (R) e.g. T mod P = R = 0
    • This can be accomplished when F = (2^n)*M mod P
  • The receiver divides incoming message T with P and if there is no remainder there is no errors

CRC Example

  • M = 101110
  • P = 1001
  • n = 3 bits (P size is n+1 e.g. n = 4-1=3)
  • 2^n *M = 101110000
  • F = 2^n*M/P = 011
  • T = 101110011

Error correction code

  • Codes that not only know there is transmission error but can locate the erronous bit/bits
  • multiplying the sent bits 01 → 000111
    • slows down communication
  • Vertical and horizontal parity bits
    • Message is divided in n * m bit blocks
    • parity bit is calculated for each row and column
    • Single erronous bit can be fixed.
  • convolutional codes
  • turbo codes

Hamming code

  • Error correcting code with minimum hamming distance of 3
    • can correct one bit error and detect 2 bit errors in message.
  • General rules
    1. All bit positions that are powers of two are used as parity bits. (positions 1, 2, 4, 8, 16 …)
    2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17
    3. Each parity bit calculates the parity for the bits in the code word in sequence determined by its position
      • starting from the position p=2^n, calculate parity for p bits and then skip nxt p bits
        • e.g. n=0, p=1, parity calculated from 1,3,5,7,9,11…
          n=1, p=2 parity 2,3,6,7,10,11 …
          n=2,p=4 : 4,5,6,7,12,13,14,15…

Example Hamming (7,4)

  • Hamming code for four bits of data with three parity bits (3+4=7)
    • Hamming distance 3
  • Message 0110
    • encoded: _ _0_110
    • parity bit 2^0=1 from locations 1,3,5,7 = 0,1,0 = 1 → 1_0_110
    • parity bit 2^1=2 from locations 2,3,6,7 = 0,1,0 = 1 → 110_110
    • parity bit 2^2=4 from locations 4,5,6,7 = 1,1,0 = 0 → 1100110
  • parity bit 1 dependent on data bits 1,2,4. pbit2 from 1,3,4 and pbit4 from 2,3,4
    • single bit transmission error will cause two parity bits be faulty and thus we can find the faulty bit

Secure Hash and MAC functions

  • Secure hash
    • Function that provides set size hash value from message
    • the resulting hash is collision resistant it is hard to find y so that h(x)=h(y) and it is hard to find x and y so that h(x)=h(y)
    • one bit change in data will change the whole hash result
  • MAC (message authenticatin code)
    • e.g. hash with key
    • protects against data alteration attacks

What method to choose?

  • If you need to protect against intentional changes on bits (e.g. attacks) then use signed secure hashes or MACs
    • otherwise use error detection or correction codes
  • error detection requires less additional bits than error correction codes
    • efficiency = d /(d+p) where d is data bits and p is the additional code bits
  • additional bits require for error correction is justified when
    • channel is oneway (e.g. broadcast type communication)
    • there is high latency
      • informing about error and retransmitting the data takes long time
    • There is high BER ratio
      • retransmission is likely to be corrupted too.

Efficiency

Last modified: 2013/07/01 14:42