University of Southampton
Faculty of Engineering and Applied Science
Department of Electronics and Computer Science

 

A project report submitted for the award of
BSc Computer Science

 

Project supervisor: Dr Paul W Garratt

Second supervisor: Dr Ken S Thomas

 

 

 

Adaptive Error Correction on a Noisy, Low-bandwidth Link

by Matthew James Bennion
18 November, 2006

 


Abstract

 

This project aims to investigate and demonstrate an adaptive error correction system on a low-bandwidth link.  The system provides optimum use of bandwidth under varying noise levels by dynamically measuring the error level and adjusting the error correction scheme employed.  At low noise levels, the system detects errors using a checksum and resends corrupt data (ARQ), which is bandwidth-efficient.  At high noise levels, the system encodes data using error-correcting codes (FEC), which are less efficient but work at higher noise levels than ARQ.  The receiver subsystem measures the noise level on the link and sends a noise model back to the transmitter subsystem.  The transmitter then uses the noise model to select an ARQ or FEC scheme that will cope with the current noise level.

 

The project includes transmitter and receiver programs that allow a user to send images over a serial cable link.  The programs use software to simulate noise, since truly random noise would be difficult to control, and display performance measures.  The programs demonstrate adaptive error correction by allowing the user to vary the noise level during transmission.

 

The results show that the adaptive error correction system provides error-free data transfer with the high efficiency of ARQ at low noise levels and the high reliability of FEC at high noise levels.

 


Contents

Acknowledgements............................................................................................................. 5

1      Introduction................................................................................................................. 6

1.1   Aim......................................................................................................................... 6

1.2   Document Conventions............................................................................................ 6

1.3   Background............................................................................................................ 6

1.4   Specific Application Area........................................................................................ 7

1.5   System Overview.................................................................................................... 7

2      System Specification & Definitions............................................................................... 8

3      Review of Approaches................................................................................................ 9

3.1   Terminology............................................................................................................ 9

3.2   System Model......................................................................................................... 9

3.3   Classification of Channels........................................................................................ 9

3.4   Classification of Noise and Errors.......................................................................... 10

3.5   Classification of Error Control Methods................................................................. 11

3.5.1    Automatic Repeat Request (ARQ)................................................................. 11

3.5.2    Sliding Window ARQ.................................................................................... 12

3.5.3    Forward Error Correction (FEC)................................................................... 13

3.5.4    Hybrid ARQ................................................................................................. 13

3.6   Examples of FEC Codes....................................................................................... 14

3.6.1    Hamming Codes............................................................................................ 14

3.6.2    BCH Codes.................................................................................................. 14

3.7   Checksums........................................................................................................... 15

3.7.1    Parity Bits..................................................................................................... 15

3.7.2    Polynomial Cyclic Redundancy Check (CRC)................................................ 15

3.8   Encoder and Decoder Synchronisation................................................................... 16

4      Prototyping............................................................................................................... 18

4.1   Prototype 1 – Serial Communication in Microsoft Visual C++................................ 18

4.2   Prototype 2 – Noise generator............................................................................... 18

4.3   Prototype 3 - JPEG Library Tester........................................................................ 19

5      System Design........................................................................................................... 20

5.1   Environment.......................................................................................................... 20

5.2   Object Oriented Design......................................................................................... 20

5.3   Choice of FEC and ARQ Systems......................................................................... 21

5.4   Packet Structure.................................................................................................... 22

5.5   Pseudo-code for Transmitter and Receiver............................................................. 23

5.6   Design of Graphical User Interface (GUI).............................................................. 24

5.7   Development, Demonstration & Release Versions.................................................. 25

6      Implementation.......................................................................................................... 27

6.1   Engineering Practices............................................................................................. 27

6.2   JPEG Library........................................................................................................ 27

6.3   BCH and Checksum Algorithms............................................................................ 28

6.3.1    Optimisations................................................................................................ 28

6.3.2    Choice of BCH parameters........................................................................... 28

6.4   Noise Model......................................................................................................... 29

6.5   Transmitter and Receiver Programs........................................................................ 29

6.6   Noise model to ADEC model transformation......................................................... 30

7      Testing...................................................................................................................... 31

7.1   During-Implementation testing................................................................................ 31

7.2   Black Box Testing & Fine-tuning the Noise Model Transformation......................... 31

7.3   White Box Testing................................................................................................. 34

8      Comparisons with Similar Work................................................................................ 35

8.1   The Ubiquitous Communications Project (Ubicom)................................................ 35

8.2   A Hybrid ARQ Scheme with Adaptive Forward Error Correction for Satellite Communications (HAFEC)         35

9      Conclusions & Future Developments......................................................................... 37

10    Glossary.................................................................................................................... 39

11    References................................................................................................................ 41

 

Appendices:

 

A1     Design Rethinks...................................................................................................... 42

A2     Project Error Log.................................................................................................... 44

A3     Black box testing..................................................................................................... 46

A4     White Box Testing................................................................................................... 50

A5     Maintaining ADEC.................................................................................................. 55

A6     User Manual........................................................................................................... 60

 

 


1         Acknowledgements

 

Implementation of BCH algorithms © 1994-7, Robert Morelos-Zaragoza.  All rights reserved.

 

Implementation of checksum computation algorithm © 1994, Craig Bruce.

 

This software is based in part on the work of the Independent JPEG Group.

 

The author wishes to thank Dr Paul Garratt and Dr Ken Thomas for their advice in completing this project, Mr Rob Salter for the original suggestion of adaptive error correction, Mr Marc Riggs for proof-reading the text and Miss Jessica Stoves for her support.

 


2         Introduction

2.1        Aim

 

The aim of this project is to investigate, and develop a system to demonstrate, adaptive error correction on low-bandwidth data links with variable noise levels. 

 

The author invented the project.

 

2.2        Document Conventions

 

This document refers to the system that this project implements as “ADEC”, for ADaptive Error Correction.

 

Where a sub-section heading has a reference, that reference covers material throughout that sub-section.  A reference before a full stop covers only the preceding sentence; a reference after a full stop covers the preceding paragraph.

 

Terms in the glossary appear bold the first time they occur in the text.  Terms appearing as sub-section headings do not appear in the glossary.

 

2.3        Background

 

It is possible to transfer data over an arbitrarily noisy link with any desired level of reliability and accuracy by sending redundant error detection and correction data alongside the original data [[1]].  However, this extra data reduces the proportion of the link’s capacity available for user data.  Furthermore, for a given level of reliability, the error correction data introduces an overhead that increases with the noise level.

 

On links with a constant noise level, the designer may anticipate the noise level at design time.  He / she may choose an appropriate level of error correction to give a good compromise between reliability and overhead.

 

On links with a varying noise level, the designer cannot anticipate the noise level on the link.  For example, factors outside the designer’s control, such as atmospheric effects and electrical interference, may influence the noise level on a radio link.

 

In situations where factors outside the designer’s control influence the noise level, the designer can use an adaptive error correction system.  An adaptive system varies the error correction capability of a communication system depending on the noise level of the link.  When the link is quiet, the system uses very little overhead to maximise throughput of user data.  The system detects if the link becomes noisy and increases the overhead to guarantee reliable data transfer at the expense of throughput.

 

2.4        Specific Application Area

 

The inspiration for ADEC is the need to transfer data reliably using TETRA digital radios [[2]].  The key features of TETRA radios relevant to ADEC are:

 

·        28.8Kb duplex data link

·        Short range (~3km radio-to-radio, ~50km radio-to-base or base-to-radio)

·        Unreliable point-to-point connection

·        Standard RS-232 interface

 

Due to the high cost and limited availability of TETRA radios, ADEC will use a cable to link two computers.  Using a cable also overcomes the difficulty in controlling errors on a radio link, which by their nature are random.  ADEC will start with a reliable cable link and use software to introduce user-controllable errors.

 

2.5        System Overview

 

Figure 1 shows a high-level view of the system.  The transmitter passes user data to an encoder, which adds error correction data.  The encoder then passes the combined data to a scrambler, which introduces errors under software control to simulate the noise on a radio link.

 

The scrambler sends this corrupt data over a cable link (which ADEC assumes to be error-free) to a decoder.  The decoder attempts to remove errors from incoming data before passing the user data to the receiver.

 

Figure 1 – System overview.


3         System Specification & Definitions

 

The system will demonstrate adaptive error correction on a noisy serial link.

 

“Adaptive” means that the level of error correction increases in proportion to the number of errors.

 

“Level of error correction” means the number of errors the system is able to correct.

 

“Errors” are single bits of data inverted during transmission  (0 becomes 1 or vice versa).

 

The serial link will be an RS-232 cable linking either two serial ports on a single Windows NT PC or one serial port on each of two PCs.

 

Test data will be a sequence of arbitrary images.  A transmitter program will display  these images on-screen and send them over the link.  The transmitter program will also provide visual feedback on the error correction parameters in real-time.

 

Some part of the software will introduce noise by intercepting and corrupting data sent to the serial ports.  The user will be able to view and adjust the noise parameters at run-time to control the error level.

 

A receiver program will read data from the serial port and correct any errors on the line.  The receiver will display the received images on-screen.  The receiver will also provide visual feedback on the error level statistics in real-time.

 

The error correction system will provide error-free data transfer for error rates between zero errors and 1 error in 50 bits.

 

The system need only send user data in one direction.  The system will sent control data in both directions.  Errors may affect traffic in both directions.

 


4         Review of Approaches

4.1        Terminology [9]

 

In digital communication, data consists of a sequence of binary digits.  This sequence can be broken down into message blocks of length k bits.  An encoder uses some algorithm to transform the input message into a codeword of length n bits, where n > k.

 

4.2        System Model

 

The aim of the encoder is to find an optimum error control strategy depending on the noise conditions on the link.  The decoder must analyse the errors on incoming data and report back to the encoder via a noise model.  The most useful parameter in a noise model is the bit error rate (BER), but historical data is also useful.

 

Parameters such as packet size and error correction level (ECL) characterise the encoder’s operation.  For adaptive error control, the system needs to transform the noise model into suitable encoder parameters in real time (Figure 2).

 

Figure 2 – The decoder produces a model of the noise on the link.  The system transforms this model into control inputs for the encoder.

 

4.3        Classification of Channels

 

Communication links have different characteristics.  A channel is a model that abstracts a number of links with some common characteristics.  The choice of error control system depends on the type of channel, so this section reviews some channels and their properties.

 

A discrete memoryless channel (DMC) is a channel that conveys digital data.  “Memoryless” means that the probability of incorrectly decoding a given bit is not affected by any previous transmissions. [3]

 

A binary symmetric channel is a DMC that transmits binary data and has a uniform noise distribution.  It is equally likely that a 1 will be received as 0 and vice versa. [3]

 

A Rayleigh fading channel alternates gradually between low and high noise levels.  For example, slowly changing atmospheric conditions may cause slowly changing noise levels on radio links.[need to find reference for this]  Rayleigh fading channels are particularly prone to burst errors (see section 4.4), because during periods of high noise levels, there will be many consecutive errors.

 

This project considers the binary symmetric channel, since this model covers all modern digital data links, including satellites, microwave and mobile radio.  However, the project will use Rayleigh fading to demonstrate adaption.

 

4.4        Classification of Noise and Errors

 

Noise is any unwanted, spurious signal superimposed on a transmitted signal.  Noise may or may not cause errors.

 

A link may suffer from random or burst errors [[3]].  A random error is a single bit, considered in isolation, inverted during transmission.  A burst error begins and ends with an erroneous bit, although the bits in-between may or may not be corrupt.  The burst length is the number of bits between two successive erroneous bits including the two incorrect bits.  Furthermore, the last erroneous bit in a burst and the first erroneous bit in the following burst must be separated by B or more correct bits, where B is the length of the error burst. [4]

 

The distinction between burst and random errors is vague.  Any sequence of B random errors, separated by at least B correct bits, is equivalent to a burst of length B.  However, burst length is a useful concept in some error correction systems.

 

All links suffer from Gaussian noise, which is random noise present in all electrical equipment and at all radio frequencies.  A designer may reduce the effects of Gaussian noise to any desired level by increasing the link’s signal strength, but in real systems, design constraints impose a limit on signal strength.  Even a well-designed system will suffer at the limits of its range or in unfavourable conditions.

 

All links (except optical fibres) suffer from electrical noise.  Common causes are circuit switching, high power electrical equipment and lightning.  Electrical noise tends to corrupt groups of consecutive bits, causing a burst error.

 

Rayleigh fading channels suffer from occasional periods of high noise levels.  High noise levels lead to an increase in random errors.

 

4.5        Classification of Error Control Methods [[4]]

4.5.1       Automatic Repeat Request (ARQ)

 

In an ARQ system, the encoder sends user data as a sequence of blocks, known as packets or frames.  The encoder computes a checksum (see section 4.7) for each packet and sends the checksum with the data.  When the decoder receives a packet, it re-computes the checksum on the user data and compares it with the checksum sent by the encoder.  If the two differ, a transmission error has occurred, and the transmitter asks the receiver to re-send the corrupt packet.

 

When a link has few or no errors, ARQ has a very low overhead.  Ethernet, for example, uses a 4-byte checksum to detect errors in up to 1,500 bytes of user data, giving an overhead of less than 1%. [[5], 23]

 

The main problem with ARQ is that the transmitter must re-send an entire packet when just a single error occurs.  For a large packet size, this is very inefficient.  “Saturation” occurs when errors occur in one packet and all subsequent retransmissions of that packet, such that no error-free data ever reaches the user.  This happens when the bit error rate is one per packet or more.  The flat “floor” of Figure 3 represents saturation.

 

Figure 3 – Graph showing usable capacity for different bit error rates and number of bits between errors.  The flat floor (usable capacity = 0) represents saturation.

 

I propose the following method for finding the efficiency of an ARQ system.  If k is the message size in bits, c is the number of checksum and header bits and b is the bit error rate, then the probability of an error in a packet .  So on average, a proportion r of all packets contain errors and need to be resent.  Since the proportion of user data in each packet is , the overall efficiency, e, is given by , or:

Equation 1

 

There are two basic types of ARQ: idle RQ (also known as stop-and-wait) and continuous RQ.  Continuous RQ may use either a selective repeat or a go-back-N retransmission strategy.

 

In an idle RQ system, the transmitter holds only one outstanding packet at a time and is idle until the receiver sends an acknowledgement signal (ACK) for that packet.  If the transmitter does not receive an ACK within a certain length of time, it repeatedly retransmits the packet.  If the transmitter does not receive an ACK after a certain number of retransmissions, the link is unusable or the receiver is not working.  Since the link is idle while the transmitter waits for an ACK, idle RQ does not use bandwidth optimally.

 

The receiver may alternatively, or additionally, send a negative acknowledgement signal (NAK), indicating that a packet contained error(s). 

 

In a continuous RQ system, the transmitter sends a continuous stream of packets without waiting for acknowledgements.  When the receiver detects an error in a packet, it asks the transmitter to re-send the packet.  The transmitter must buffer each packet until the receiver acknowledges that packet.  The transmitter gives each packet a unique sequence number, which the receiver uses to tell the transmitter which packets to retransmit.

 

In a go-back-N system, the transmitter re-sends the corrupt and all subsequent packets whether they were corrupt or not.  This means that the receiver does not need to buffer any packets, but the transmitter wastes bandwidth by re-sending error-free packets.

 

In a selective repeat system, the transmitter re-sends only the corrupt packets.  The receiver must have enough buffer space to store any further packets received before the transmitter re-sends the corrupt packets.

 

Continuous RQ with selective repeat is the most bandwidth-efficient form of ARQ, but requires the most complexity and buffer space in the receiver and transmitter.

 

4.5.2       Sliding Window ARQ [[6]]

 

Sliding window systems give each packet a sequence number, allowing the transmitter to send and re-send packets out of order.  The transmitter stores previously sent packets for possible retransmission.  The receiver stores out-of-order packets until it receives all preceding packets.  A sliding window receiver need not acknowledge each packet immediately – an acknowledgement for a packet implies acknowledgement for all previous packets.  This is a problem for an adaptive system, which requires immediate acknowledgement of each packet to ensure fast response to changing error conditions.  The extra storage requirements and sequencing make sliding window a complicated protocol.

4.5.3       Forward Error Correction (FEC)

 

In a FEC system, the encoder adds redundant error correction data to the user data according to some algorithm.  The decoder uses the extra data not only to detect but also locate and correct errors.

 

FEC systems are based on the mathematical coding theory.  This report will not concentrate on the theory, since implementations are freely available on the World Wide Web [[7]].  However, a designer needs some background knowledge to choose a suitable code for an application.

 

Block codes split user data into fixed-sized blocks.  Convolution codes work on continuous data streams. A code may exist in block and convolution forms, but ADEC will look only at block codes.

 

The Hamming or minimum distance, dmin, of a code is the minimum number of bits that differ between any two codewords [3].  The Hamming distance of a code determines its error correcting ability, t, which is the maximum number of bit errors a code can correct [8].  dmin is the minimum burst length for which a code can correct errors.  Typically [3],

 

Equation 2

 

The notation [n, k] describes a block code, where n is the number of bits transmitted for every k bits of user data (some sources use the notation [n, k, dmin]).  The ratio k / n is r, the rate of the code.

 

A code may have both binary and non-binary versions.  This refers to the size of the field used in the encoding and decoding algorithms (field theory is outside this project’s scope).  The distinction between binary and non-binary does not affect a code’s error correcting properties, but binary codes tend to have simpler encoding and decoding algorithms. [[8]]

 

A code may have both systematic and non-systematic versions.  In systematic codes, the codeword consists of the unaltered message with the check digits appended.  In non-systematic codes, the message digits are not present in the codeword.  Again, this difference affects the mathematical properties of the codes and algorithms, but not the error correcting capabilities [8].

 

4.5.4       Hybrid ARQ

 

Any system using both ARQ and FEC is a hybrid system.  An example is the type-II hybrid ARQ system [[9], [10]], which uses incremental redundancy.  Upon detecting an error, the receiver repeatedly asks the transmitter to send additional error correction data until the receiver is able to correct all the errors.

 

An incremental redundancy system suffers from some problems.  For example, the transmitter assumes the link is error-free the first time it transmits each frame, rather than adapting to historical error data.  Therefore the receiver’s requests for additional data incur an overhead, which would not be present in a pure FEC system.  Also the retransmission requests themselves may succumb to errors.

 

4.6        Examples of FEC Codes

4.6.1       Hamming Codes

 

Hamming codes are a simple form of systematic block error correction code [[11]].  They allow correction of a single bit error and detection an even number of errors per block.  They will neither detect nor correct an odd number of errors greater than three.  Encoding k bits of user data requires an additional log2(k) + 1 bits.  So with a block size of 18 bits, this is a [24, 18] code of rate 0.75.

 

Figure 4 shows how the number of additional bits varies with increasing block size.

Figure 4 – Graph showing how number of check bits varies with block size for Hamming codes.

 

4.6.2       BCH Codes

 

Bose, Chaudhuri and Hocquenghem (BCH) codes, also known as redundant residue polynomial codes, are a generalisation of Hamming codes for multiple-error correction [[12], [13]].  BCH codes exist that can correct any number of errors, but higher error correction capabilities incur greater overheads.  Codes only exist for certain combinations of message length k, codeword length n and number of errors t.  For example, codes only exist for , where and m ł 3, and for  [3].

 

Figure 5 shows the rate (or efficiency) of BCH codes for various values of t and n.

Figure 5 – Graph showing the rate of BCH codes for various values of t and n.

 

4.7        Checksums

 

A checksum is a number calculated from a message by the encoder.  The encoder appends the checksum to the message before transmission.  The decoder performs the same calculation on the received data, and compares the result to the checksum transmitted by the encoder.  With an ideal checksum, any error(s) in the transmitted data will cause the decoder’s checksum to differ from the encoder’s checksum.

 

4.7.1       Parity Bits

 

A simple form of checksum is the parity bit.  The encoder and decoder agree on whether to use odd or even parity.  The encoder then appends a parity bit to each message.  The encoder chooses the parity bit such that the total number of 1’s transmitted (including the parity bit) is odd (for odd parity) or even (for even parity).  If the decoder receives an even number of 1’s (for odd parity) or an odd number of 1’s (for even parity), then some of the bits are erroneous.

 

This scheme only detects an odd number of bit errors, since an even number of bit errors will result in the same value of the parity bit.

 

4.7.2       Polynomial Cyclic Redundancy Check (CRC) [[14]]

 

This method computes an n-bit checksum for a k-bit message, where n < k, using an (n + 1)-bit number known as the generator polynomial.  The encoder (or decoder) multiplies the message by 2n, then divides modulo-2 the result by the generator polynomial.  The remainder after this division is the checksum.

 

Any error pattern that is identical to, or has a factor identical to the generator polynomial, results in the same checksum as the correct transmission, so the error will go undetected.  Therefore the generator polynomial should be prime (modulo-2) to eliminate factors and reduce the possibility of undetected errors. [4]

 

A CRC using a prime n-bit generator polynomial can detect all single, double, triple and odd number of bit errors, all burst errors of length less than n, and ‘most’ burst errors of length greater than n.  (For example, a CRC using a 16-bit generator can detect 99.997% of 17-bit burst errors and 99.998% of 18-bit burst errors.)

 

4.8        Encoder and Decoder Synchronisation

 

In a communication system, the decoder will receive input from the link as a continuous stream of data.  If the link is particularly noisy, the decoder may receive spurious input even when the transmitter is not sending any data.  To decode packets correctly, the decoder needs to know where in the continuous stream of input each packet begins and ends.

 

The decoder also needs to know what type of error correction the encoder used for each packet.  Since packets can be variable-sized, the decoder also needs to know the size of each packet, so that it can determine where one packet ends and the next starts.  A solution is to prepend a header, containing size and encoding method, to each packet [4].  The format of the header is pre-defined, so upon receiving a header, the decoder knows the size and encoding method of the associated packet.

 

Low error rate systems, such as Internet Protocol and Ethernet networks, use a checksum to detect errors in the header.  Asynchronous Transfer Mode networks use Hamming codes (see section 4.6.1) to correct single errors in the header.  Checksums and Hamming codes are low-overhead forms of error control.  ADEC needs to work on high-error links, which necessitates high-overhead error correction.  Ideally, ADEC would apply adaptive error correction to the header as well as the user data, but this is difficult to achieve.

 

In the following discussion, I assume that retransmission request packets are small and encoded using the highest ECL.  If the highest ECL is not able to correct all the errors on a link, the link is too noisy for ADEC to work..

 

My first idea was for the encoder to use the highest available ECL for the first packet sent after the transmitter starts operating.  The first packet would not contain any user data, but would contain the size and ECL of the next packet.  Therefore the decoder would be able to decode the first packet by assuming the highest ECL and using the pre-defined header structure.  Thereafter, the header of the nth packet would contain the ECL and size of the (n + 1)th packet.  The encoder would use the same ECL for both a header and its associated packet, to achieve adaptive error correction on both header and user data.

 

However, the above system would not be reliable in practice.  If the decoder is unable to decode correctly the nth packet, the encoder will at some point retransmit the nth packet using a higher ECL.  The decoder will not know what ECL the encoder used when re-transmitting the nth packet.  The decoder could make an assumption, such as the next highest ECL, but the decoder might fail to decode the retransmitted version.  The encoder would then retransmit the nth packet using successively higher ECLs.  Since some of these retransmissions may be corrupt, the decoder would not be certain of the size and ECL of any given packet.  Thus the encoder and decoder would lose synchronisation and no further communication would be possible.

 

An alternative is to encode all headers using the highest ECL.  Each header contains the size and ECL of its associated packet, so the decoder can decode any packet independently of the others.  If the encoder uses the highest ECL on all headers, this introduces an unnecessary overhead when the link is not noisy.  However, if the header is small, the overhead is not excessive.

 

This also solves the problem of synchronisation.  Suppose the header is m bits long.  If the decoder can correctly decode the first m bits of the input stream, then these m bits are a valid header.  So the decoder knows the size and ECL of the subsequent packet.  If the decoder cannot decode the first m bits, the decoder traverses the input stream one bit at a time trying to decode m-bit blocks of data.  Upon correctly decoding a block as a header, the decoder knows the size and ECL of the next packet.  If the decoder fails to decode any m-bit blocks within a specified length of time, the link is unusable or the transmitter is not sending any data.

 

 


5         Prototyping

5.1        Prototype 1 – Serial Communication in Microsoft Visual C++

 

I made a prototype to determine how to control a PC’s serial ports and handle bitmaps using Microsoft Visual C++ and Microsoft Foundation Classes (MFC).  This took about 30 hours.

 

Figure 6 shows the transmitter program.  The user can load an image (stored in the program’s executable file) and transmit it over the selected serial port.  The user can configure all serial port settings from a pop-up dialogue box.

 

Figure 6 – Transmitter prototype.

 

The receiver program is similar.  A “receive” button replaces the “load image” and “transmit once” buttons.  The receiver waits in an idle state until data arrives at the serial port and displays the received image.

 

This prototype demonstrated the following:

·        Loading and manipulating bitmaps, both as high-level objects within the MFC framework and on a pixel-by-pixel basis;

·        Serial port operation including opening, closing, configuring and sending and receiving data;

·        Use of worker threads to handle data transfer as a background operation;

·        Use of a null-modem cable as an error-free link.

 

5.2        Prototype 2 – Noise generator

 

I extended Prototype 1 to include a simple error generator (additive white Gaussian noise).  The most difficult part of this prototype was implementing a logarithmic slider control (Figure 7).  This will be useful for the final program.

 

Figure 7 – Logarithmic slider.

5.3        Prototype 3 - JPEG Library Tester

 

Prototypes 1 and 2 used a hard-coded Windows bitmap to store the image.  The final program will use JPEGs, since these are highly compressed and thus ideal for use on low-bandwidth links.  I obtained a JPEG library from the Internet [[15]] and wrote a simple prototype to load, decode and display JPEG files (Figure 8).

 

Figure 8 – JPEG library tester prototype.

 

 


6         System Design

6.1        Environment

 

ADEC will run on an IBM PC or compatible computer running Microsoft Windows NT, version 4, service pack 3, since this is a widespread and readily available platform.  ADEC will use the Microsoft Visual C++ compiler version 5.0 and the Microsoft Foundation Classes (MFC) model, since the designer is familiar with this programming environment.  Furthermore, MFC saves the programmer considerable time by providing a large range of relevant library functions and a graphic user interface (GUI) framework.

 

6.2        Object Oriented Design

 

I designed ADEC’s class hierarchy using the Object Modelling Technique as implemented by SELECT OMT Enterprise edition.  Figure 9 and Figure 10 show the main class diagrams for the Transmitter and Receiver programs respectively.  The accompanying CD-ROM contains the SELECT project, which includes full descriptive text and function parameters and return values.  Anyone needing to understand ADEC in the future will find the SELECT project useful.

 

Figure 9 – Class diagram for Transmitter program.

Figure 10 – Class diagram for Receiver program.

 

6.3        Choice of FEC and ARQ Systems

 

ADEC will use binary BCH codes for FEC, since these offer good performance, and encoding and decoding algorithms are available as C source code on the World Wide Web [7].  ADEC will use codes of order , which is an arbitrary choice but convenient, since tables of parameters exist for these codes [3].

 

ADEC will use a 32-bit CRC checksum for ARQ.  Practical systems (such as Ethernet and the Internet Protocol) demonstrate that 32-bits is a workable size for a CRC.

 

ADEC will have a maximum packet size of 511 bytes for ARQ.  The maximum packet size, together with the link’s speed, determines ADEC’s response time to sudden changes in the noise level.  On a 28.8kbps link with one stop bit and no parity,  511 bytes takes 0.16 seconds to transmit, which is therefore the response time.  If the maximum packet size is too small, ADEC will be inefficient when the noise level is low.  511 bytes gives an efficiency of 96% with a 16 byte header and 4-byte checksum.

 

When FEC is in use, the packet size will be 100 bytes and will not vary depending on noise conditions (since t is varied).  100 bytes corresponds to a BCH code with ADEC’s maximum order m and error correction capability t.

 

A designer may alter both ARQ and FEC packet sizes in a particular application.  However, extremely large values require a large header, which is inefficient (see section 4.8) and lowers ADEC’s response time.  Extremely small values are inefficient due to the overhead of the header.

 

ADEC will use a slight variant of idle RQ.  The decoder will send both ACKs and NAKs for user data, so that the encoder knows as soon possible whether the last packet was successfully decoded without waiting for timeouts.  However, the decoder will not send anything if it fails to decode a header, since the decoder will use incorrect headers to synchronise with the encoder (see section 4.8).

 

ADEC will not use sliding window ARQ, which is generally more efficient than idle RQ, because ADEC needs as small a header as possible (see section 4.8).  Sliding window ARQ adds a sequence number and free window space to the header.  Also, ADEC aims to be a investigation and development system, so does not need optimum performance; sliding windows add unnecessary complication.

 

If the transmitter sends a packet and does not receive a valid ACK or NAK within a pre-set time period, the transmitter will re-send the packet up to 20 times before declaring the link unusable.  The transmitter and receiver will use a timeout when attempting to synchronise (see section 4.8) and to recover from a link that is too noisy for ADEC to work.  All operations accessing the serial ports will use a timeout to recover from physical link errors (such as lack of hardware flow control).

6.4        Packet Structure

 

ADEC will send all integers least significant byte first.  Each packet must contain an integral number of bytes, between 1 and 507 inclusive, of user data (with a 4-byte checksum, the maximum packet size is 511, the largest number that fits into a 9-bit binary number).

 

The ADEC model and noise model classes contain serialise and de-serialise methods, which allow ADEC to send ADEC model and noise model objects over the link.  The serialise methods produce a sequence of bytes that represents an object’s data members.  The de-serialise methods accept a sequence of bytes and use these bytes to fill the object’s data members.

 

The transmitter will prepend the following header to each packet it sends, as illustrated in Figure 11.  When ARQ is in use, the first 32 bits following the header will be the checksum for the user data.

 

·        FEC flag: 1 if FEC is in use, 0 if ARQ is in use;

·        Code index;

·        Packet size in bytes;

 

Figure 11 – Header structure.

 

The receiver will send an ACK or NAK for each packet it receives.  The receiver will use the highest ECL for ACK and NAK packets.  This will give acknowledgement packets the best chance of reaching the transmitter.

 

An acknowledgement packet will contain the following information, as illustrated in Figure 12.

 

·      Type (0 for ACK, 1 for NAK);

·      BER of last packet, scaled to an unsigned 16-bit integer;

·      Average BER, scaled to an unsigned 16-bit integer;

·      Minimum distance between errors of last packet.

 

Figure 12 – Acknowledgement packet structure.

 

6.5        Pseudo-code for Transmitter and Receiver

 

The following pseudo-code shows the operation of the transmitter.

 

bytesToSend = total size of user data

attempts = 0

 

while ( bytesToSend > 0 ) and ( attempts < MAX_ATTEMPTS )

do

if attempts = 0

       then   Encode user data

              lastPacketSize = number of user data bytes encoded

              Encode header data

       end if

 

       if scrambler_in_use

       then   Scramble user data

              Scramble header data

       end if

 

       result = Transmit header data

       if ( result = timeout ) or ( result = failure ) or ( result = user aborted )

       then   exit

       end if

 

       result = Transmit user data

       if ( result = timeout ) or ( result = failure ) or ( result = user aborted )

       then   exit

       end if

 

       result = Receive feedback

       if ( result = timeout ) or ( result = failure ) or ( result = user aborted )

       then   exit

       end if

 

       timeout = GetTime + FEEDBACK_TIMEOUT

       while ( Decode feedback = failure ) and ( GetTime < timeout )

       do

              discard first bit of feedback

              Receive next bit of feedback

       end while

 

       if Decode feedback = success

       then   Deserialise feedback into noise model

              Transform noise model into ADEC model

       else

              exit

       end if

 

       if feedback = ACK

       then   bytesToSend -= lastPacketSize

              attempts = 0

       else

              attempts += 1

       end if

 

end while

 

The following pseudo-code shows the operation of the receiver.

 

bytesToRead = number of bytes to read

 

while bytesToRead > 0

 

       result = Receive header

       if ( result = timeout ) or ( result = failure ) or ( result = user aborted )

       then   exit

       end if

 

       timeout = GetTime + HEADER_TIMEOUT

       while ( Decode header = failure ) and ( GetTime < timeout )

       do

              Discard first bit of header

              Receive next bit of header

       end while

 

       if Decode header = success

       then   Deserialise header into an ADEC model

              packetSize = number of bytes specified in header

       else

              exit

       end if

 

       result = Receive packet

       if ( result = timeout ) or ( result = failure ) or ( result = user aborted )

       then   exit

       end if

 

       result = Decode packet

       Update noise model with this packet's errors

 

       if result = success

       then   bytesToRead -= packetSize

              Store decoded packet data in a buffer

              Transmit noise model + ACK

       else

              Transmit noise model + NAK

       end if

 

end while

 

6.6        Design of Graphical User Interface (GUI)

 

Microsoft Visual C++ simplifies the design of a Windows program.  The designer produces the GUI using a graphical editor, and provides code that the application will execute when the user interacts with the GUI, for example by pressing buttons and selecting menu options.  Visual C++ provides all intermediate code.

 

The transmitter program needs to load and display a sequence of image files and invoke the transmitter object to send each image.  The receiver program need only display received images.

 

Both programs will allow the user to configure the serial ports using a Microsoft library function.  The programs will allow the user to select the simulated noise level on the link.  The programs will provide visual feedback about the type and number of errors on the link, and the ECL.

 

Figure 13 shows the user interface design for the transmitter and receiver programs.  The user will load one or more image files into the transmitter and transmit these files as a continuous sequence.  The receiver is either idle, allowing the user to configure the serial port, or receiving, when the program continually listens for and displays images.  The user may move the noise slider control at any time, to simulate the effects of a Rayleigh fading channel.

 

Both programs will use separate worker threads for communications and encoding / decoding functions. Worker threads allow the user to continue manipulating the program, in particular to adjust the error rate and abort an operation, while the program is busy.  The worker threads will communicate with the main program threads by shared memory, message passing and events.

 

 

Figure 13 – Design of Transmitter (left) and Receiver (right) program user interfaces.

6.7        Development, Demonstration & Release Versions

 

For development and demonstration purposes, the designer needs to be able to control and examine the performance of ADEC at run-time.  However, in a practical device such as a TETRA radio, ADEC would run on an embedded computer.  On an embedded computer, ADEC would not have a user interface and would provide reliable data transfer transparently to the user, and without user intervention.

 

Figure 14 shows the data flow diagram for ADEC.  To produce a transparent, embedded version of ADEC, a developer would disable the scrambler module (for example, by a pre-processor macro).  The developer would then replace the transmitter and receiver user interface modules with some other applications which need error-free communication.  To this end, the interface between the transmitter and receiver and their respective user-interfaces is minimal and simple (see Figure 9 and Figure 10).

 

A developer may choose to alter some parameters, such as maximum packet size, to suit a particular application (see section 8.2 and Appendix A5).

 

ADEC runs on Windows NT but could be ported to run on any operating system that supports processes, messaging and events.

 

Figure 14 – ADEC Data Flow Diagram (GUI feedback not shown).

 


7         Implementation

 

This section describes the main issues and problems encountered during coding.

 

7.1        Engineering Practices

 

ADEC implements a variety of good software engineering practices.

 

All code is well-commented and formatted, as shown in Table 1.  All identifiers are meaningful.  All functions, their arguments and return values are commented.

 

Table 1 – Quantity and proportion of types of source code line.

Type of line

Number of lines

Percentage of total lines

Code

4807

75%

Block comments

500

8%

In-line comments

671

10%

Blank

1139

18%

 

 

ADEC tests for the success of all heap memory allocations, and handles failures without exiting the program (where possible).  ADEC displays informative message boxes for all errors and program execution continues where possible.  There are no memory leaks (verified using Visual C++ tools and the Windows NT task manager).

 

The code uses pre-processor macros instead of numeric constants wherever possible.  This improves maintainability, as numbers that might change in future releases (such as packet and header sizes) appear in just one place.

 

Several pre-processor macros determine how the compiler builds ADEC.  Defining “__GUI_FEEDBACK” includes code to display feedback on the GUI.  Files common to both transmitter and receiver use the “__CADECTXDLG” macro to determine whether to compile transmitter- or receiver-specific code.  Defining the “SCRAMBLER” macro includes code to add noise to the link in software (see Appendix A6.7).

 

7.2        JPEG Library

 

ADEC uses JPEG [[16]] image compression.  JPEG supports variable compression ratios, but higher ratios degrade image quality.  Useful ratios are between 10:1 and 100:1.

JPEG uses complicated mathematics, so I chose to use a library available on the Internet [15].  This library is well-tested, open and very reliable.

 

7.3        BCH and Checksum Algorithms

 

I obtained C source code for the functions gen_poly, encode_bch, ­decode_bch, generate_gf and the initial values of the array p from the World Wide Web [7].  These functions implement the BCH algorithms.  I had insufficient time to learn the necessary  mathematics and implement these functions myself.  This code constitutes 10% of the total program code.

 

I also obtained a checksum generator from the World Wide Web [7].  This constitutes less than 1% of the total program code.

 

During testing, I discovered that the BCH decoder sometimes did not report a failure when a packet contained too many errors to correct.  I solved this by including a CRC with FEC (as well as ARQ) packets.

 

7.3.1       Optimisations

 

The BCH algorithms store a single bit in a byte (eight bits).  It is possible to modify the algorithms to store eight bits in a byte, which would reduce both storage requirements and memory accesses by a factor of eight.  However, to access a single bit, the algorithms would need to perform bitmask and bitshift operations, introducing an overhead of 8 x 2 = 16 operations per byte.  I have chosen not to store eight bits in each byte, since this would be difficult to implement.  Also, a modern CPU’s cache is large enough (for example, 16kB level 1 and 512kB level 2 on a Pentium II [[17]] ) to hold all the data that the algorithms use (typically 10k), so the additional memory accesses will not significantly slow the algorithms down.

 

7.3.2       Choice of BCH parameters

 

Figure 5 shows that, for a given error correction capability, the efficiency of a code increases as the size of a code increases.  However, the code size should be small for small packets to make efficient use of the transmission channel.  The nature of BCH codes limits the range of possible code sizes (see section 4.6.2), so there will be some inefficiency if the user data size is not divisible by k for a particular code.  This is unavoidable, although in general a transmitter may reduce inefficiency by combining a sequence of small packets into a larger packet [[18]].  ADEC does not aim to implement a optimised protocol stack, so does not perform this optimisation.

 

There is no easy way to calculate the number of user data bits k per codeword for a BCH code of length n and error correcting capability t [3, [19]]. However, the encoder must find n, m and k at run-time to generate the code.  I propose the following solution.

 

Suppose the user wishes to encode c bits of data with an error correction capability of t.  We need a BCH code of codeword length.  The codeword must also include n – k redundancy bits, and we know that n – k is at most mt [3].

 

Equation 3 and Equation 4 give values for m and n large enough to accommodate c and t.  The BCH encoding algorithm computes k at run-time as a side effect.

 

Equation 3

 

Equation 4

 

I implemented and verified this method, but then decided to use a look-up table containing the 232 combinations of BCH parameters supported by ADEC.  This means that a header need only contain an 8-bit index into the look-up table, rather than n, m, k and t, which saves valuable header space.  However, developer wishing to use larger BCH codes would find Equation 3 and Equation 4 useful (see Appendix A5).

 

The size of a packet may be larger than k for a given BCH code.  In this case, ADEC breaks the packet into k-bit chunks, encodes each chunk separately and concatenates the encoded chunks (this functionality is not part of the BCH algorithms as obtained from the Internet).

 

7.4        Noise Model

 

The noise model class computes the average BER and minimum distance using an  exponential weighted average, so that,

 

Equation 5

 

where  is the nth average value, dn is the nth data value and .  This method gives more weight to recent data and accounts for all previous data without having to store the previous data.

 

7.5        Transmitter and Receiver Programs

 

I created transmitter and receiver programs using Microsoft Visual C++ AppWizard, which provides skeleton code to which extra functionality can be added.

 

Programming the extra functionality took several weeks as I had to discover and learn several features of Windows programming not used in the prototypes, including:

 

·        Making GUI objects such as buttons change position when a window is resized;

·        Making a window resize itself to accommodate different-sized images;

·        Setting a minimum size for a window;

·        Adding a grip image to the corner of a dialog box to use when resizing;

·        Using MFC message maps to handle Windows system events;

·        Displaying an hourglass to indicate that the program is busy.

 

I originally intended that the worker threads would use events to communicate with the main threads.  However, waiting on an event blocks the waiting thread, which prevents the user interacting with the GUI.  Instead, I used Windows messages, which allow fully asynchronous communication between threads.

 

The transmitter and receiver programs contain a single instance of the transmitter and receiver classes respectively.

 

7.6        Noise model to ADEC model transformation

 

This section describes transformation that the transmitter performs on the noise model that the receiver includes with each ACK or NAK.  A developer may change constants mentioned in this section to adjust performance as described in Appendix A5.  The transmitter chooses one of the transformations described below according to the previous packet’s state.

 

If the previous packet used ARQ and succeeded, ADEC sets the maximum size for the next packet to 30% larger than the last packet, up to the maximum ARQ packet size.

 

If the previous packet used ARQ and failed, ADEC sets the maximum size for the next packet to 30% smaller than the last packet.  If this calculation gives a packet size less than 16 bytes (the minimum ARQ packet size), ADEC switches to FEC mode.  A limitation of ARQ is that the CRC calculation does not give the number of bit errors that caused the failure.  ADEC assumes a BER of 1 in 10 (the maximum supported BER) for failed ARQ packets, but if this assumption is incorrect, ADEC may choose an inappropriate level of error correction.  Therefore ADEC maintains a measure of efficiency as shown in Equation 6.  If efficiency falls below 50%, ADEC switches to FEC, which gives the true BER.

 

Equation 6

 

 

If the previous packet used FEC, ADEC computes the efficiencies of using ARQ, using Equation 1, and FEC, by dividing the user data size of a packet by the sum of the encoded data, header and CRC sizes.  If ARQ is more efficient, ADEC switches to ARQ, using the size of the last successful ARQ packet.  If FEC is more efficient, ADEC switches to, or continues using FEC.

 

If ADEC decides to use FEC, the maximum packet size is 100 bytes.  If the previous packet failed, ADEC does not know how many errors were in the failed packet, and simply doubles the error correction capability up to the maximum of 255.  If the previous packet succeeded, ADEC uses an error correction capability of twice the BER (actually an exponential weighted average of the BER).  Using twice the actual BER reduces the chances of the packet failing given the random nature of the BER.

 


8         Testing

 

The testing procedure used for ADEC is split into three phases – during-implementation testing, black box and white box testing.  Appendices A3 and A4 contain the test reports and Appendix A2 contains the project error log.  I have assumed that the BCH implementations, checksum generator and JPEG library are error free.  This is a valid assumption because the code is open, widely used and mature.

 

8.1        During-Implementation testing

 

The first testing phase took place during coding.  I used the compiler to detect syntax and typographical errors.  As I completed each class, I ran the program until a crash occurred and then located and fixed the error(s).  This testing phase ended when the program performed all major functions consistently without crashing.

 

The code contained a large number of trivial errors, but since I fixed them within minutes of finding them, I have not documented them.

 

The project error log (Appendix A2) lists all errors that took more than 30 minutes to fix together with their dates and solutions.

 

8.2        Black Box Testing [[20]] & Fine-tuning the Noise Model Transformation

 

Black box tests exercise a program over its full range of inputs.  ADEC has only two inputs – image file(s) of varying size(s) and the noise level.  However, I devised further tests to exercise important functions individually.  Appendix A3 describes the tests I performed and their results.  ADEC passed most of the tests first time.  The project error log includes all errors found by black box testing and their solutions.

 

Black box testing also includes performance testing.  ADEC does not aim to meet any real-time requirement but rather to show how adaptive error correction improves efficiency on a noisy link.  Therefore the performance tests show efficiency against BER.  Efficiency here means user data as a proportion of total data; total data includes headers, checksums, error correction data and any retransmissions.

 

Figure 15 (and Appendix A3.2) shows the results of performance tests.  For input data, I used 22 JPEG files between 2,925 and 4,843 bytes in size.  For each BER, I ran the transmitter and receiver programs until the efficiency, as displayed in the feedback areas (see Appendix A6), stabilised to within two percentage points (between 2 and 5 minutes).  All these tests used exactly the BER shown, that is, every xth bit is incorrect for a BER of 1 in x.

 

Section 7.6 describes Transformation A.  For BERs up to 1 in 30,000, ADEC achieves its maximum efficiency of 0.95.  As the BER increases to 1 in 4,000, the efficiency falls steadily, until ADEC switches to FEC.  The efficiency then rises to 0.67, the maximum efficiency of FEC, and then falls again as the FEC overhead increases.  The efficiency drops rapidly to zero at very high BERs.

For Transformation B, I increased the ARQ-to-FEC switchover point, as described in Appendix A5.4.  This should move the “hump” (that is, BER between 1 in 2,000 and 1 in 200) to the left, increasing the efficiency for BERs around 4,000.  I also added code to reduce the FEC packet size when the efficiency falls below 0.3.  This should reduce the fall-off rate of efficiency at BER > 1 in 40, since in Transformation A uses a fixed FEC packet size, which leads to very inefficient BCH codes at high error rates.

 

With transformation B, ADEC worked with BERs up to 1 in 20.  Although the efficiency at BER = 1 in 4,000 increased slightly compared to Transformation A, short term changes in the efficiency caused ADEC to reduce the packet size at BER = 200, turning the hump into a trough.

 

Therefore, for Transformation C, I changed the threshold for reducing the FEC packet size to efficiency = 0.15, and only if the ECL is within 20% of its maximum.  This should retain the hump of Transformation A, but avoid the rapid fall-off at very high BERs.

 

While testing Transformation C, I noticed that the low efficiency (0.02 or less) of BCH codes with t > 127 caused the drop in efficiency at BER = 200 in Transformation B.  Therefore I reduced the maximum value of t from 255 to 127 (Figure 15 shows Transformation C with the maximum t of 127).  This allowed me to remove the code for reducing the FEC packet size (larger FEC packets are more efficient – see Figure 5).

 

I decided not to reduce the ARQ-to-FEC switchover point further, since the extra time taken to encode packets with FEC offsets the slight increase in efficiency.

 

Figure 15 – Efficiency against BER for various noise model transformations.  BER is exact, that is, every xth bit is incorrect for a BER of 1 in x.

 

I then tested Transformation C with the “exact” checkbox on the transmitter and receiver programs disabled, giving a pseudo-random BER with an average equal to the value that the user selects (using the noise slider GUI control).  The results, shown in Figure 16 and Appendix A3.2, are similar to those for exact BERs.   However, the graph shows considerable random variation, due to idiosyncrasies of the C++ random number generator (see Appendix A3.1).  Also, the efficiency for random BERs falls to ADEC’s minimum efficiency (that is, the highest ECL) at a lower BER than for exact BERs.  This is because the BER is random, so the actual BER will sometimes be higher than the requested BER.  For this reason, measurements at BERs of 1 in 40 and higher tend to fail because the BER occasionally exceeds 1 in 10, which is too high for ADEC.

 

Figure 16 – Graph of efficiency against BER for exact and random BERs.

 

ADEC fails with exact BERs of 1 in 20 but works with random BERs of up to 1 in 10.  This is because the burst length varies randomly.  With an exact BER, once the burst length falls to dmin, FEC fails on every packet, but with a random BER, some packets will (randomly) have a burst length greater than dmin, and thus succeed.

 

To clarify this, consider a code with length 100 bits and error correcting capability 10.  From Equation 2, dmin = 2t + 1 = 21.  If 10 equally spaced errors occur (Figure 17(a)), the burst length will be 10, less than dmin, so the code will fail.  However, if 10 randomly spaced errors occur (Figure 17(b)), the burst length may be greater than dmin, so the code may succeed.

 

Figure 17 – Distribution of errors within a packet.

 

8.3        White Box Testing

 

I performed basis-path white box testing on ADEC.  Basis-path testing uses specially chosen input data to force the execution of every line of code at least once, giving a high probability of finding errors [20].  I used the following method, which is simpler than the conventional method of flow-path analysis [20].

 

1.      Use the Visual C++ profiler tool to show which lines of code the computer executed while running ADEC.

2.      Look at lines not executed, and choose input data to force their execution.  In many cases, I had to modify the source code temporarily to test error-handling code.

3.      Run ADEC again and merge the profiler’s output with the output from the previous run.

4.      Repeat step 3 until the profiler reports that the computer has executed every line.

 

Appendix A4 contains the full test report.

 

 

 


9          Comparisons with Similar Work

9.1        The Ubiquitous Communications Project (Ubicom) [[21]]

 

Ubicom aims to transmit multimedia data over a high-bandwidth (150 Mbps) local area radio network for mobile users.  Like ADEC, Ubicom uses adaptive FEC, but does not switch to ARQ at low error rates.  Ubicom allows higher-level applications to choose a quality of service, that is, to tolerate some errors in exchange for better efficiency.  This approach is good for data such video, which requires high throughput (and hence efficiency), but can tolerate some errors which a human would not notice.

 

Although it uses images as test data, ADEC is a general-purpose system that assumes all data transfers must be error-free.  Therefore ADEC provides a single quality of service – zero errors – to higher-level applications.

 

Apart from quality-of-service and bandwidth differences, ADEC and Ubicom are similar.

 

9.2        A Hybrid ARQ Scheme with Adaptive Forward Error Correction for Satellite Communications (HAFEC) [[22]]

 

Like ADEC, HAFEC uses ARQ for low BERs and adaptive FEC for high BERs.  However, the systems differ in the way the transmitter determines the BER, and the transmission control system used.

 

In ADEC, the receiver uses data from the BCH decoder to estimate the BER.  The receiver then sends a noise model back to the transmitter.  This works because ADEC uses stop-and-wait transmission control, so the transmitter receives a response, and hence the current BER, for each packet.

 

However, HAFEC uses a satellite channel, which is characterised by a long propagation delay.  The transmitter would have to wait 0.6s for each acknowledgement, which is inefficient.  Therefore the receiver only sends NAKs, and the transmitter estimates the BER from the proportion of NAKed packets.  In HAFEC, transmitter encodes headers using the same ECL as for data.  This means that, upon failing to decode a header, the receiver does not know what ECL to use for the user data and incorrectly decodes all subsequent data until the transmitter times out.  ADEC encodes the header using the maximum available ECL, so the receiver always knows the ECL to use for the data (unless the link is too noisy for ADEC anyway).  An advantage of the HAFEC approach is smaller headers.  An advantage of the ADEC approach is less data loss due to failed headers.

 

Figure 18 shows the predicted efficiency of HAFEC.  The “proposed ARQ/FEC” curve is equivalent to the random BER curve of Figure 16, and shows that ADEC and HAFEC perform similarly.

Figure 18 – Graph of predicted efficiency against BER for HAFEC (“proposed ARQ/AFEC”), a stop-and-wait ARQ system (“REJ”) and an ideal selective repeat ARQ system (“ideal SREJ”).  Reproduced from [22].

 


10    Conclusions & Future Developments

 

(See also section 8.2 for further discussion of results.)

 

ADEC shows that adaptive error correction provides better efficiency than either ARQ or FEC alone on links with variable noise levels.  Figure 19 shows how ADEC compares with Ethernet (a typical ARQ-only system [[23]]) and a FEC-only system.  To give a fair comparison, the Ethernet data assumes a frame size of 507 bytes, which is ADEC’s maximum packet size, and the FEC data assumes a fixed BCH code of length 1023 bits and error correcting capability 127, equivalent to ADEC’s highest ECL.

 

ADEC is typically slightly less efficient than Ethernet due to the smaller packet size and extra overhead of transmitting an ADEC model with each packet.  However, ADEC continues to work at error rates where Ethernet (or any practical ARQ system) fails.  Compared to a fixed FEC system, ADEC is more efficient at low error rates.  Figure 19 shows that ADEC fails at BER = 1 in 20, while the equivalent FEC system fails at BER = 1 in 10.  However, a developer can alter the BCH codes available to ADEC to work at any desired BER.  Figure 19 shows that the efficiency rises when ADEC switches to FEC only, (BER = 1 in 2,000).  A developer may move this rise to the left (see section 8.2).  However, the longer time taken to encode FEC packets may offset any benefits of a more linear graph.

Figure 19 – Graph comparing efficiencies of ADEC, Ethernet and FEC at different BERs.

 

ADEC’s basic operation is independent of the noise-to-ADEC model transformation and noise model structure.  This allows a system designer easily to tailor ADEC to the noise conditions on a given link.  In particular, ADEC fails at BERs greater than 1 in 10 and has a worst-case efficiency of 11% (see section 8.2).  The designer may easily adjust these values by using longer BCH codes (see Appendix A5), or investigate different error correction codes [3].

 

ADEC is a demonstration system and the BCH algorithms are too slow for practical use (for example, ADEC takes about one second to encode and decode 100 bytes using the highest ECL on a 233 MHz Pentium II PC).  Faster algorithms exist [[24]], but not as freely available source code.  ADEC’s BCH algorithms have considerable scope for optimisation, such as working one word (32 bits) rather than one bit at a time (see section 7.3.1).  Implementing the algorithms in machine code would also improve their speed.  It is possible to produce even faster hardware implementations of the BCH algorithms [9].  Existing hardware designs only support fixed code parameters, but a designer might either use fewer codes, each with dedicated hardware (which would give coarser adaptability), or modify existing designs to support variable parameters.  However, adaptive FEC may prove too slow for a particular application.

 

Another area of future work is developing the noise model transformation.  The current transformation does not tackle any particular noise pattern.  However, the developer of a real adaptive system would analyse the noise patterns of a given link tailor the transformation to meet system requirements.

 

The current transformation is iterative – it tries small variations in parameters until a good level of efficiency is reached.  To avoid local minima, the transformation cross-checks the results of the iterative approach with certain known facts, such as that ARQ is always more efficient than FEC for packets over a given size.  However, future work might investigate neural networks for finding the optimum parameters for a given noise pattern.  Alternatively, a genetic algorithm, which uses evolution as a form of optimisation [[25]], might prove useful in finding optimum parameters.  (See also [[26]].)

 

Overall, ADEC meets its aims by demonstrating the higher efficiency of adaptive error correction over fixed error detection / correction systems.


11    Glossary

 

Bit error rate (BER): the rate at which bit errors occur with respect to the number of bits sent over a link.  BER = number of bit errors / number of bits sent.

 

Check digits: redundant digits or bits that an encoder adds to a message to allow a decoder to correct or detect errors.

 

Code: a one-to-one mapping from a set of messages to a set of codewords.

 

Codeword: the result of encoding a message.

 

Efficiency: in the context of a particular error correction code, efficiency is the ratio of user data to error correction data, that is the rate of the code.  In a broader sense, efficiency is the ratio of user data to total data, including all headers, checksums and error correction data, that a system sends over a link.

 

Error correction level (ECL): the maximum number of errors that an error correction system is able to correct.  The packet size, choice of FEC or ARQ, checksum length, FEC generator polynomial and other information may specify an ECL.

 

Exponential weighted average: an average in which the weight given to previous values diminishes exponentially with respect to ‘age’ (where age can be chronological or other, such as sequential order).  Computed by , where . Larger values of a give more weight to recent data.

 

Message: a sequence of user data bits that an encoder encodes.

 

Propagation delay: the time taken for a signal to travel from a transmitter to a receiver.

 

Rate: the ratio r of the number of bits k in each message to the number of bits n in the corresponding codeword.  That is, r = k / n.  This is equivalent to the efficiency of a code.

 

Sequence number: a unique number that identifies an individual packet in a sequence of packets.

 

Worker thread: a thread that handles background tasks that the user shouldn't have to wait for before continuing to use an application.

 


12    References

 

References to Internet documents include the date of access.



[[1]] Shannon, C.E.: “A Mathematical Theory of Communication”, Bell System Technical Journal, vol. 63, 1948.

[[2]] European Telecommunications Standards Institute; www.etsi.fr/tetra/tetra.htm (standards agreed but not made public at time of writing).

[[3]] Lin, S., and Costello, D.J.: “Error Control Coding: Fundamentals and Applications”, Prentice-Hall, 1983.

[[4]] Halsall, F.: “Data Communications, Computer Networks And Open Systems”, Addison-Wesley, 1996.

[[5]] Peterson, L.L. et al.: “Computer Networks: A Systems Approach”, Morgan Kaufman Publishers, 1996.

[[6]] Tanenbaum, A.S.: “Computer Networks” (2nd edition), Prentice-Hall, 1990.

[[7]] Morelos-Zaragoza, R.: “The Error Correcting Codes (ECC) Home Page”,

http://imailab.iis.u-tokyo.ac.jp/~robert/codes.html.

[[8]] Jones, G.A.: Verbal communication, Department of Mathematics, University of Southampton, 24th November 1998.

[[9]] Lin, S., Costello, D.J., and Miller, M.: “Automatic repeat request error control schemes”, IEEE Communications Magazine, December 1984, 22, pp. 5-17.

[[10]] Krishna, H., and Morgera, S.D.: “A new error control scheme for hybrid ARQ systems”, IEEE Transactions on Communications, October 1987, COM-35, pp. 981-989.

[[11]] Hamming, R.W.: “Error detecting and error correcting codes”, Bell System Technical Journal, vol. 26, 1950, pp. 147-160.

[[12]] Hocquenghem, A.: “Codes corecteurs d’erreurs”, Chiffres, vol. 2, 1959, pp. 147-156.

[[13]] Bose, R.C., and Chaudhuri, D.K.: “On a Class of Error Correcting Binary Group Codes”, Information and Control, vol. 3, March 1960, pp. 68.79.

[[14]] Ramabadroan, T., and Gaitonde, S.: “A Tutorial on CRC Computations”, IEEE Micro, August 1988, pp. 62-75.

[[15]] Independent JPEG Group, http://www.ijg.org, 31st March 1999.

[[16]] Joint Photographic Experts Group (JPEG), http://www.jpeg.org, 31st March 1999.

[[17]] “Intel® Pentium® II Processor”, http://www.intel.com/design/PentiumII/prodbref, 31st March 1999.

[[18]] Comer, D.E. and Stevens, D.L.: “Internetworking with TCP/IP: principles, protocols and architecture”, Prentice-Hall, New Jersey, 1988.

[[19]] Mann, H.B.: “On the Number of Information Symbols in Bose-Chaudhuri Codes”, Information and Control, no. 5, pp. 153-162, June 1962.

[[20]] Pressman, R.S.: “Software Engineering – A Practitioner’s Approach” (3rd edition), McGraw Hill, London, 1994.

[[21]] Delft University of Technology: “The Ubiquitous Communications Project”, http://ubicom.twi.tudelft.nl, 15th April 1999.

[[22]] Shiozaki, A. et al.: “A Hybrid ARQ Scheme with Adaptive Forward Error Correction for Satellite Communications”, IEEE Transactions on Communications, vol. 39, no. 4, April 1991.

[[23]] The Institute of Electrical and Electronics Engineers (IEEE): “IEEE 802.3, 1998 Edition”, IEEE Standards, 1998.

[[24]] Chen, C.L.: “High-Speed Decoding of BCH Codes”, IEEE Transactions on Information Theory, vol. 27, pp.254-256, March 1981.

[[25]] “Computational Engineering and Design Centre (CEDC)”, http://www.soton.ac.uk/~ajk/opt/welcome.html, 14th April 1999.

[[26]] Kousa, M. and Turner, L.: “Reliability-throughput optimisation for adaptive forward error correction systems”, IEE proceedings Communications, vol. 143, no. 6, December 1996.