wszystko 4GNWK67HBOU52Z4WYUC4E2EC4YTNAEOP2DY3SGQ


HDLC - A Technical Overview

High-Level Data Link Control, also know as HDLC, is a bit oriented, switched and non-switched protocol. It is a data link control protocol, and falls within layer 2, the Data Link Layer, of the Open Systems Interface(OSI) model as shown in figure 1.

0x01 graphic

Figure 1

HDLC is a protocol developed by the International Organization for Standardization(ISO). It falls under the ISO standards ISO 3309 and ISO 4335. It has found itself being used throughout the world. It has been so widely implemented because it supports both half duplex and full duplex communication lines, point to point(peer to peer) and multi-point networks, and switched or non-switched channels. The procedures outlined in HDLC are designed to permit synchronous, code-transparent data transmission. Other benefits of HDLC are that the control information is always in the same position, and specific bit patterns used for control differ dramatically from those in representing data, which reduces the chance of errors.

It has also led to many subsets. Two subsets widely in use are Synchronous Data Link Control(SDLC) and Link Access Procedure-Balanced(LAP-B).

This technical overview will be concerned with the following aspects of HDLC:

HDLC STATIONS AND CONFIGURATIONS

HDLC specifies the following three types of stations for data link control:

PRIMARY STATION

Within a network using HDLC as it's data link protocol, if a configuration is used in which there is a primary station, it is used as the controlling station on the link. It has the responsibility of controlling all other stations on the link(usually secondary stations). Despite this important aspect of being on the link, the primary station is also responsible for the organization of data flow on the link. It also takes care of error recovery at the data link level(layer 2 of the OSI model).

SECONDARY STATION

If the data link protocol being used is HDLC, and a primary station is present, a secondary station must also be present on the data link. The secondary station is under the control of the primary station. It has no ability, or direct responsibility for controlling the link. It is only activated when requested by the primary station. It only responds to the primary station. The secondary station's frames are called responses. It can only send response frames when requested by the primary station.

COMBINED STATION

A combined station is a combination of a primary and secondary station. On the link, all combined stations are able to send and receive commands and responses without any permission from any other stations on the link. Each combined station is in full control of itself, and does not rely on any other stations on the link. No other stations can control any combined station.

HDLC also defines three types of configurations for the three types of stations:

UNBALANCED CONFIGURATION

The unbalanced configuration in an HDLC link consists of a primary station and one or more secondary stations. The unbalanced occurs because one stations controls the other stations. In a unbalanced configurations, any of the following can be used:

An example of an unbalanced configuration can be found below in figure 2.a

BALANCED CONFIGURATION

The balanced configuration in an HDLC link consists of two or more combined stations. Each of the stations have equal and complimentary responsibility compared to each other. Balanced configurations can used only the following:

An example of a balanced configuration can be found below in figure 2.b

Figure 2.a An unbalanced configuration

0x01 graphic

Figure 2.b A balanced configuration

0x01 graphic

SYMMETRICAL CONFIGURATION

This third type of configuration is not widely in use today. It consists of two independent point to point, unbalanced station configurations. In this configurations, each station has a primary and secondary status. Each station is logically considered as two stations.

HDLC Operational Modes

HDLC offers three different modes of operation. These three modes of operations are:

Normal Response Mode

This is the mode in which the primary station initiates transfers to the secondary station. The secondary station can only transmit a response when, and only when, it is instructed to do so by the primary station. In other words, the secondary station must receive explicit permission from the primary station to transfer a response. After receiving permission from the primary station, the secondary station initiates it's transmission. This transmission from the secondary station to the primary station may be much more than just an acknowledgment of a frame. It may in fact be more than one information frame. Once the last frame is transmitted by the secondary station, it must wait once again from explicit permission to transfer anything, from the primary station. Normal Response Mode is only used within an unbalanced configuration.

Asynchronous Response Mode

In this mode, the primary station doesn't initiate transfers to the secondary station. In fact, the secondary station does not have to wait to receive explicit permission from the primary station to transfer any frames. The frames may be more than just acknowledgment frames. They may contain data, or control information regarding the status of the secondary station. This mode can reduce overhead on the link, as no frames need to be transferred in order to give the secondary station permission to initiate a transfer. However some limitations do exist. Due to the fact that this mode is Asynchronous, the secondary station must wait until it detects and idle channel before it can transfer any frames. This is when the ARM link is operating at half-duplex. If the ARM link is operating at full-duplex, the secondary station can transmit at any time. In this mode, the primary station still retains responsibility for error recovery, link setup, and link disconnection.

Asynchronous Balanced Mode

This mode uses combined stations. There is no need for permission on the part of any station in this mode. This is because combined stations do not require any sort of instructions to perform any task on the link.

Normal Response Mode is used most frequently in multi-point lines, where the primary station controls the link. Asynchronous Response Mode is better for point to point links, as it reduces overhead. Asynchronous Balanced Mode is not used widely today.

The "asynchronous" in both ARM and ABM does not refer to the format of the data on the link. It refers to the fact that any given station can transfer frames without explicit permission or instruction from any other station.

HDLC Non-Operational Modes

HDLC also defines three non-operational modes. These three non-operational modes are:

The two disconnected modes(NDM and ADM) differ from the operational modes in that the secondary station is logically disconnected from the link(note the secondary station is not physically disconnected from the link). The IM mode is different from the operations modes in that the secondary station's data link control program is in need of regeneration or it is in need of an exchange of parameters to be used in an operational mode.

HDLC Frame Structure

HDLC uses the term "frame" to indicate an entity of data(or a protocol data unit) transmitted from one station to another. Figure 3 below is a graphical representation of a HDLC frame with an information field.

Figure 3 An HDLC frame with an information field.

0x01 graphic

Field Name

Size(in bits)

Flag Field( F )

8 bits

Address Field( A )

8 bits

Control Field( C )

8 or 16 bits

Information Field( I )

Variable; Not used in some frames

Frame Check Sequence( FCS )

16 or 32 bits

Closing Flag Field( F )

8 bits

THE FLAG FIELD

Every frame on the link must begin and end with a flag sequence field(F). Stations attached to the data link must continually listen for a flag sequence. The flag sequence is an octet looking like 01111110. Flags are continuously transmitted on the link between frames to keep the link active. Two other bit sequences are used in HDLC as signals for the stations on the link. These two bit sequences are:

The time between the transmission of actual frames is called the interframe time fill. The interframe time fill is accomplished by transmitting continuous flags between frames. The flags may be in 8 bit multiples.

HDLC is a code-transparent protocol. It does not rely on a specific code for interpretation of line control. This means that if a bit at position N in an octet has a specific meaning, regardless of the other bits in the same octet. If an octet has a bit sequence of 01111110, but is not a flag field, HLDC uses a technique called bit-stuffing to differentiate this bit sequence from a flag field. Once the transmitter detects that it is sending 5 consecutive 1's, in inserts a 0 bit to prevent a "phony" flag.

At the receiving end, the receiving station inspects the incoming frame. If it detects 5 consecutive 1's it looks at the next bit. If it is a 0, it pulls it out. If it is a 1, it looks at the 8th bit. If the 8th bit is a 0, it know an abort or idle signal has been sent. It then proceeds to inspect the following bits to determine appropriate action. This is the manner in which HDLC achieves code-transparency. HDLC is not concerned with any specific bit code inside the data stream. It is only concerned with keeping flags unique.

THE ADDRESS FIELD

The address field(A) identifies the primary or secondary stations involvement in the frame transmission or reception. Each station on the link has a unique address. In an unbalanced configuration, the A field in both commands and responses refers to the secondary station. In a balanced configuration, the command frame contains the destination station address and the response frame has the sending station's address.

THE CONTROL FIELD

HDLC uses the control field(C) to determine how to control the communications process. This field contains the commands, responses and sequences numbers used to maintain the data flow accountability of the link, defines the functions of the frame and initiates the logic to control the movement of traffic between sending and receiving stations. There three control field formats:

The frame is used to transmit end-user data between two

devices.

The control field performs control functions such as acknowledgment of frames, requests for re-transmission, and requests for temporary suspension of frames being transmitted. Its use depends on the operational mode being used.

This control field format is also used for control purposes. It is used to perform link initialization, link disconnection and other link control functions.

THE POLL/FINAL BIT(P/F)

The 5th bit position in the control field is called the poll/final bit, or p/f bit. It can only be recognized when it is set to 1. If it is set to 0, it is ignored. The poll/final bit is used to provide dialogue between the primary station and secondary station. The primary station uses P=1 to acquire a status response from the secondary station. The P bit signifies a poll. The secondary station responds to the P bit by transmitting a data or status frame to the primary station with the P/F bit set to F=1. The F bit can also be used to signal the end of a transmission from the secondary station under Normal Response Mode.

THE INFORMATION FIELD

This field is not always in a HDLC frame. It is only present when the Information Transfer Format is being used in the control field. The information field contains the actually data the sender is transmitting to the receiver.

THE FRAME CHECK SEQUENCE FIELD

This field contains a 16 bit, or 32 bit cyclic redundancy check. It is used for error detection.

HDLC COMMANDS AND RESPONSES

The set of commands and responses in HDLC is summarized in table 1.

INFORMATION TRANSFER FORMAT COMMAND AND RESPONSE

The functions of the information command and response is to transfer sequentially numbered frames, each containing an information field, across the data link.

SUPERVISORY FORMAT COMMANDS AND RESPONSES

Supervisory(S) commands and responses are used to perform numbered supervisory functions such as acknowledgment, polling, temporary suspension of information transfer, or error recovery. Frames with the S format control field cannot contain an information field. A primary station may use the S format command frame with the P bit set to 1 to request a response from a secondary station regarding its status. Supervisory Format commands and responses are as follows:

UNNUMBERED FORMAT COMMANDS RESPONSES

The unnumbered format commands and responses are used to extend the number of data link control functions. The unnumbered format frames have 5 modifier bits which allow for up to 32 additional commands and 32 additional response functions. Below, 13 command functions, and 8 response functions are described.

TABLE 1 HDLC Commands and Responses

Information Transfer

Information Transfer

Format Commands

Format Responses

I - Information

I - Information

Supervisory Format

Supervisory Format

Commands

Responses

RR - Receive ready

RR - Receive ready

RNR - Receive not ready

RNR - Receive not ready

REJ - Reject

REJ - Reject

SREJ - Selective reject

SREJ - Selective reject

Unnumbered Format

Unnumbered Format

Commands

Commands

SNRM - Set Normal Response Mode

UA - Unnumbered Acknowledgment

SARM - Set Asynchronous Response Mode

DM - Disconnected Mode

SABM - Set Asynchronous Balanced Mode

RIM - Request Initialization Mode

DISC - Disconnect

RD - Request Disconnect

SNRME - Set Normal Response Mode Extended

UI - Unnumbered Information

SARME - Set Asynchronous Response Mode Extended

XID - Exchange Identification

SABME - Set Asynchronous Balanced Mode Extended

FRMR - Frame Reject

SIM - Set Initialization Mode

TEST - Test

UP - Unnumbered Poll

UI - Unnumbered Information

XID - Exchange identification

RSET - Reset

TEST - Test

HDLC SUBSETS

Many other data link protocols have been derived from HDLC. However, some of them reach beyond the scope of HDLC. Two other popular offsets of HDLC are Synchronous Data Link Control(SDLC), and Link Access Protocol, Balanced(LAP-B). SDLC is used and developed by IBM. It is used in a variety of terminal to computer applications. It is also part of IBM's SNA communication architecture. LAP-B was developed by the ITU-T. It is derived mainly from the asynchronous response mode(ARM) of HDLC. It is commonly used for attaching devices to packet-switched networks.

Bibliography

Texts

  1. Black, Ulyess. Data Networks: Concepts, Theory and Practice, Prentice-Hall, United States, 1989

  2. Freeman, Roger L. Practical Data Communications, John Wiley & Sons, Inc., United States, 1995

  3. Freeman, Roger L. Reference Manual For Telecommunications Engineering, John Wiley & Sons, Inc., Canada, 1994

  4. Folts, Harold C. McGraw-Hill's Compilation of Open Systems Standards Vol. 2, McGraw-Hill

  5. Held, Gilbert, Data Communications Networking Devices, John Wiley & Sons, Inc., England, 1992

Internet Web Sites

  1. Notes, Images and other Miscellania

http://www.cs.indiana.edu/l/www/classes/a247-whit/misc.html

To jest wersja html pliku http://reedsolomon.tripod.com/Slide2.doc.
G o o g l e automatycznie generuje wersję html dokumentu podczas przeglądania strony.
Aby połączyć się z tą stroną lub ją zatwierdzić, użyj następującego adresu url: http://www.google.com/search?q=cache:kcqfg6TTRr4C:reedsolomon.tripod.com/Slide1.doc+%22reed-solomon+code%22&hl=pl&ie=UTF-8

Google nie jest w żaden sposób związany z autorami tej strony i nie jest odpowiedzialny za jej treść.

Znalezione słowa zostały podświetlone: 

reed 

solomon 

code 

0x01 graphic

Reed Solomon codes are a subset of BCH codes and are linear block codes. A Reed-Solomon code is specified as RS(n,k) with s-bit symbols.

This means that the encoder takes k data symbols of s bits each and adds parity symbols to make an n symbol codeword. There are n-k parity symbols of s bits each. A Reed-Solomon decoder can correct up to t symbols that contain errors in a codeword, where 2t = n-k.

The following diagram shows a typical Reed-Solomon codeword (this is known as a Systematic code because the data is left unchanged and the parity symbols are appended): 

Example: A popular Reed-Solomon code is RS(255,223) with 8-bit symbols. Each codeword contains 255 code word bytes, of which 223 bytes are data and 32 bytes are parity. For this code:

n = 255, k = 223, s = 8

2t = 32, t = 16

The decoder can correct any 16-symbol errors in the code word: i.e. errors up to 16 bytes anywhere in the codeword can be automatically corrected.

Given a symbol size s, the maximum codeword length (n) for a Reed-Solomon code is n = 2s - 1

For example, the maximum length of a code with 8-bit symbols (s=8) is 255 bytes.


 

Generator Polynomial

A Reed-Solomon codeword is generated using a special polynomial. All valid code words are exactly divisible by the generator polynomial. The general form of the generator polynomial is: 

and the codeword is constructed using:

c(x) = g(x).i(x)

where g(x) is the generator polynomial, i(x) is the information block, c(x) is a valid codeword and is referred to as a primitive element of the field.

Example: Generator for RS(255,249) 

Code for Encoding  (by Simon Rockcliff)

 

register int i,j ;

int feedback ;

   

   for (i=0;i<nn-kk;i++)  bb[i] = 0;

   for (i=kk-1; i>=0; i--)

    {  feedback = index_of[data[i]^bb[nn-kk-1]] ;

       if (feedback != -1)

        { for (j=nn-kk-1; j>0; j--)

            if (gg[j] != -1)

              bb[j] = bb[j-1]^alpha_to[(gg[j]+feedback)%nn] ;

            else

              bb[j] = bb[j-1] ;

          bb[0] = alpha_to[(gg[0]+feedback)%nn] ;

        }

       else

        { for (j=nn-kk-1; j>0; j--)

            bb[j] = bb[j-1] ;

          bb[0] = 0 ;

        } ;

    } ;

} ; 
 

Reed-Solomon Codes

An introduction to Reed-Solomon codes: principles, architecture and implementation

1. Introduction

Reed-Solomon codes are block-based error correcting codes with a wide range of applications in digital communications and storage. Reed-Solomon codes are used to correct errors in many systems including:

A typical system is shown here:

0x01 graphic

The Reed-Solomon encoder takes a block of digital data and adds extra "redundant" bits. Errors occur during transmission or storage for a number of reasons (for example noise or interference, scratches on a CD, etc). The Reed-Solomon decoder processes each block and attempts to correct errors and recover the original data. The number and type of errors that can be corrected depends on the characteristics of the Reed-Solomon code.

2. Properties of Reed-Solomon codes

Reed Solomon codes are a subset of BCH codes and are linear block codes. A Reed-Solomon code is specified as RS(n,k) with s-bit symbols.

This means that the encoder takes k data symbols of s bits each and adds parity symbols to make an n symbol codeword. There are n-k parity symbols of s bits each. A Reed-Solomon decoder can correct up to t symbols that contain errors in a codeword, where 2t = n-k.

The following diagram shows a typical Reed-Solomon codeword (this is known as a Systematic code because the data is left unchanged and the parity symbols are appended):

0x01 graphic

Example: A popular Reed-Solomon code is RS(255,223) with 8-bit symbols. Each codeword contains 255 code word bytes, of which 223 bytes are data and 32 bytes are parity. For this code:

n = 255, k = 223, s = 8

2t = 32, t = 16

The decoder can correct any 16 symbol errors in the code word: i.e. errors in up to 16 bytes anywhere in the codeword can be automatically corrected.

Given a symbol size s, the maximum codeword length (n) for a Reed-Solomon code is n = 2s - 1

For example, the maximum length of a code with 8-bit symbols (s=8) is 255 bytes.

Reed-Solomon codes may be shortened by (conceptually) making a number of data symbols zero at the encoder, not transmitting them, and then re-inserting them at the decoder.

Example: The (255,223) code described above can be shortened to (200,168). The encoder takes a block of 168 data bytes, (conceptually) adds 55 zero bytes, creates a (255,223) codeword and transmits only the 168 data bytes and 32 parity bytes.

The amount of processing "power" required to encode and decode Reed-Solomon codes is related to the number of parity symbols per codeword. A large value of t means that a large number of errors can be corrected but requires more computational power than a small value of t.

Symbol Errors

One symbol error occurs when 1 bit in a symbol is wrong or when all the bits in a symbol are wrong.

Example: RS(255,223) can correct 16 symbol errors. In the worst case, 16 bit errors may occur, each in a separate symbol (byte) so that the decoder corrects 16 bit errors. In the best case, 16 complete byte errors occur so that the decoder corrects 16 x 8 bit errors.

Reed-Solomon codes are particularly well suited to correcting burst errors (where a series of bits in the codeword are received in error).

Decoding

Reed-Solomon algebraic decoding procedures can correct errors and erasures. An erasure occurs when the position of an erred symbol is known. A decoder can correct up to t errors or up to 2t erasures. Erasure information can often be supplied by the demodulator in a digital communication system, i.e. the demodulator "flags" received symbols that are likely to contain errors.

When a codeword is decoded, there are three possible outcomes:

1. If 2s + r < 2t (s errors, r erasures) then the original transmitted code word will always be recovered,

OTHERWISE

2. The decoder will detect that it cannot recover the original code word and indicate this fact.

OR

3. The decoder will mis-decode and recover an incorrect code word without any indication.

The probability of each of the three possibilities depends on the particular Reed-Solomon code and on the number and distribution of errors.

Coding Gain

The advantage of using Reed-Solomon codes is that the probability of an error remaining in the decoded data is (usually) much lower than the probability of an error if Reed-Solomon is not used. This is often described as coding gain.

Example: A digital communication system is designed to operate at a Bit Error Ratio (BER) of 10-9, i.e. no more than 1 in 109 bits are received in error. This can be achieved by boosting the power of the transmitter or by adding Reed-Solomon (or another type of Forward Error Correction). Reed-Solomon allows the system to achieve this target BER with a lower transmitter output power. The power "saving" given by Reed-Solomon (in decibels) is the coding gain.

3. Architectures for encoding and decoding Reed-Solomon codes

Reed-Solomon encoding and decoding can be carried out in software or in special-purpose hardware.

Finite (Galois) Field Arithmetic

Reed-Solomon codes are based on a specialist area of mathematics known as Galois fields or finite fields. A finite field has the property that arithmetic operations (+,-,x,/ etc.) on field elements always have a result in the field. A Reed-Solomon encoder or decoder needs to carry out these arithmetic operations. These operations require special hardware or software functions to implement.

Generator Polynomial

A Reed-Solomon codeword is generated using a special polynomial. All valid codewords are exactly divisible by the generator polynomial. The general form of the generator polynomial is:

0x01 graphic

and the codeword is constructed using:

c(x) = g(x).i(x)

where g(x) is the generator polynomial, i(x) is the information block, c(x) is a valid codeword and a is referred to as a primitive element of the field.

Example: Generator for RS(255,249)

0x01 graphic

3.1 Encoder architecture

The 2t parity symbols in a systematic Reed-Solomon codeword are given by:

0x01 graphic

The following diagram shows an architecture for a systematic RS(255,249) encoder:

0x01 graphic

Each of the 6 registers holds a symbol (8 bits). The arithmetic operators carry out finite field addition or multiplication on a complete symbol.

3.2 Decoder architecture

A general architecture for decoding Reed-Solomon codes is shown in the following diagram.

0x01 graphic

Key

r(x)

Received codeword

Si

Syndromes

L(x)

Error locator polynomial

Xi

Error locations

Yi

Error magnitudes

c(x)

Recovered code word

v

Number of errors

The received codeword r(x) is the original (transmitted) codeword c(x) plus errors:

r(x) = c(x) + e(x)

A Reed-Solomon decoder attempts to identify the position and magnitude of up to t errors (or 2t erasures) and to correct the errors or erasures.

Syndrome Calculation

This is a similar calculation to parity calculation. A Reed-Solomon codeword has 2t syndromes that depend only on errors (not on the transmitted code word). The syndromes can be calculated by substituting the 2t roots of the generator polynomial g(x) into r(x).

Finding the Symbol Error Locations

This involves solving simultaneous equations with t unknowns. Several fast algorithms are available to do this. These algorithms take advantage of the special matrix structure of Reed-Solomon codes and greatly reduce the computational effort required. In general two steps are involved:

Find an error locator polynomial

This can be done using the Berlekamp-Massey algorithm or Euclid's algorithm. Euclid's algorithm tends to be more widely used in practice because it is easier to implement: however, the Berlekamp-Massey algorithm tends to lead to more efficient hardware and software implementations.

Find the roots of this polynomial

This is done using the Chien search algorithm.

Finding the Symbol Error Values

Again, this involves solving simultaneous equations with t unknowns. A widely-used fast algorithm is the Forney algorithm.

4. Implementation of Reed-Solomon encoders and decoders

Hardware Implementation

A number of commercial hardware implementations exist. Many existing systems use "off-the-shelf" integrated circuits that encode and decode Reed-Solomon codes. These ICs tend to support a certain amount of programmability (for example, RS(255,k) where t = 1 to 16 symbols). A recent trend is towards VHDL or Verilog designs (logic cores or intellectual property cores). These have a number of advantages over standard ICs. A logic core can be integrated with other VHDL or Verilog components and synthesized to an FPGA (Field Programmable Gate Array) or ASIC (Application Specific Integrated Circuit) - this enables so-called "System on Chip" designs where multiple modules can be combined in a single IC. Depending on production volumes, logic cores can often give significantly lower system costs than "standard" ICs. By using logic cores, a designer avoids the potential need to do a "lifetime buy" of a Reed-Solomon IC.

Software Implementation

Until recently, software implementations in "real-time" required too much computational power for all but the simplest of Reed-Solomon codes (i.e. codes with small values of t). The major difficulty in implementing Reed-Solomon codes in software is that general purpose processors do not support Galois field arithmetic operations. For example, to implement a Galois field multiply in software requires a test for 0, two log table look-ups, modulo add and anti-log table look-up. However, careful design together with increases in processor performance mean that software implementations can operate at relatively high data rates. The following table gives some example benchmark figures on a 166MHz Pentium PC:

 

Code

Data rate

RS(255,251)

12 Mbps

RS(255,239)

2.7 Mbps

RS(255,223)

1.1 Mbps

 

These data rates are for decoding only: encoding is considerably faster since it requires less computation. The benchmarks were generated using 4i2i Communications Ltd's speed optimised software implementations.

5. Further reading

In this paper we have deliberately avoided discussing the theory and implementation of Reed-Solomon codes in detail. For more detail please see the following books:

1.Wicker, "Error Control Systems for Digital Communication and Storage", Prentice-Hall 1995

2. Lin and Costello, "Error Control Coding: Fundamentals and Applications", Prentice-Hall 1983

3. Clark and Cain, "Error Correction Coding for Digital Communications", Plenum 1988

4. Wilson, "Digital Modulation and Coding", Prentice-Hall 1996

For an introduction to the applications of Error Control Codes in video communications please see:

Riley and Richardson, "Digital Video Communications", Artech House 1997 (available from http://www.artech-house.com/)

6. About the authors

This paper was written by Martyn Riley and Iain Richardson. For more details about the authors click here.

7. Reed-Solomon implementations in hardware and software

If you would like details on Reed-Solomon implementations in hardware and software then  click here.

Page maintained by Laura J.Riley

Copyright © 4i2i Communications Ltd 1996, 1997, 1998, last update 0x01 graphic

Reed-Solomon Codes and CD Encoding

Stan Hanley

April 24th, 2002

SM486 4001

Error Correcting Codes

Professor David Joyner

In the digital age, all information whether it is sound, video, graphic, or text is 0's and 1's. Just as a picture is subject to a scratch or sound is subject to noise, digital information is susceptible to error. For data to be usable, there is a method of encoding information, which is organizing the 0's and 1's, such that errors can be corrected. Digital errors are most often in the form of a 0 being received as a 1 or vice versa. One major applications of digital encoding is the audio compact disk, or CD. CDs use a modified form of the Reed-Solomon code called the Cross Interleaved Reed-Solomon Code, or CIRC. Before this can be explained in more detail, general error correcting codes will be introduced along with the Reed-Solomon code.

Codes have three primary characteristics. These characteristics are the length, dimension, and minimum distance of a code. The length of a code, or n, is the amount of bits (or information pieces) per codeword. The dimension, or k, is the amount of actual information bits contained within each codeword. Minimum distance, or d, is the minimum number of information differences between each codeword. A code is generally written as a [n,k,d] code. Coding algorithms take information and translate it into a codeword. While there is theoretically any number of coding algorithms, only a few have been implemented. This is because information must be able to be encoded and decoded relatively quickly. Also, some codes may be able to correct a huge number of errors, but that means much of the transmitted information is check bits. If check bits fill up a bandwidth, then the system is slowed down.

Minimum distance is the most important factor for determining a codes ability to correct errors. The following example is the list of codewords for the [7,4,3] Hamming code:

 


[ 0 0 0 0 0 0 0 ] [ 0 1 0 1 0 1 0 ] [ 0 1 1 0 0 1 1 ] [ 0 1 1 1 1 0 0 ] [ 1 0 0 0 0 1 1 ] [ 1 0 0 1 1 0 0 ] [ 1 0 1 0 1 0 1 ] [ 0 0 0 1 1 1 1 ] [ 0 0 1 0 1 1 0 ]

[ 0 0 1 1 0 0 1 ] [ 0 1 0 0 1 0 1 ] [ 0 1 0 1 0 1 0 ] [ 0 1 1 0 0 1 1 ] [ 0 1 1 1 1 0 0 ] [ 1 0 0 0 0 1 1 ] [ 1 0 0 1 1 0 0 ] [ 1 0 1 0 1 0 1 ]

[ 1 0 1 1 0 1 0 ] [ 1 1 0 0 1 1 0 ] [ 1 1 0 1 0 0 1 ] [ 1 1 1 0 0 0 0 ] [ 1 1 1 1 1 1 1 ]

 


Looking at the codewords, one sees that each differs from the others in at least three places. Using d, one determines how many errors a code can correct. Let C be a Hamming Code with minimum distance d. Then C is [(d-1)/2] error correcting. For example, the [7,4,3] Hamming code is 1 error correcting. If one received [1 1 0 1 1 1 0], he would notice it is not a code word. However, it would quickly be corrected to [1 1 0 0 1 1 0]. If one received [1 1 1 1 1 1 0], he would not know if it was [1 0 1 1 0 1 0] with errors in the 2nd and 5th bit, or [1 1 0 0 1 1 0] with errors in the 3rd and 4th bit.

Reed-Solomon codes are linear block codes. They are often denoted RS(n,k) with s-bit symbols. The encoder takes k data symbols and adds check symbols to make an n symbol codeword. Reed-Solomon codes correct up to t errors in a codeword where 2t=n-k. For a symbol size s, the maximum codeword length (n) is n=2s-1. Because a Reed-Solomon codes correct byte errors, they can potentially correct many bit errors. A symbol error occurs when 1 to all bits in a symbol are wrong. For example, RS(255,223) can correct 16 symbol errors. In the worst case, 16 bit errors may occur, each in a separate symbol so that the decoder corrects 16 bit errors. In the best case, 16 complete symbol errors occur so that the decoder corrects 16 x 8 bit errors. This makes a Reed-Solomon code very good at correcting large clusters of errors.

Reed-Solomon codes are based on finite field arithmetic. Each codeword is generated using a generator polynomial. All valid codewords are exactly divisible by the generator polynomial. The general form of the generator polynomial is g(x)=(x-i)(x-i+1)…( x-i+2t). The codeword is generated such that c(x)=g(x)i(x) where g(x) is the generator polynomial, i(x) is the information block, and c(x) is a valid codeword.

A received codeword is a valid codeword, c(x), plus any errors, e(x). The Reed-Solomon decoder will identify the position and magnitude of up to t errors and correct them. Any Reed-Solomon code has 2t syndromes that depend only on errors. If the roots of the generator polynomial are substituted into r(x) where r(x)=c(x)+e(x), then the syndrome is given.

The symbol error location is found by solving a simultaneous equation with t unknowns. Algorithms that do this take advantage of the matrix structure of Reed-Solomon codes. Two steps are required to find the error location. First an error locator polynomial is found. The two algorithms that find this special polynomial are the Berlekamp-Massey algorithm and Euclid's algorithm. By analyzing the errors as the elements of a finite field, the Berlekamp-Massey algorithm finds the shortest linear recurrence that will produce those elements. This algorithm usually leads to more efficient software and hardware, but Euclid's algorithm is most often used because it is easier to implement. The roots of the error location polynomial are found using the Chien search algorithm. Once the errors are located, the proper symbol is found by solving the equation with t unknowns using the Forney algorithm.

Now that Reed-Solomon codes have been introduced, we will discuss how they are used to decode errors on a CD. Audio CD's use the Red Book Standard, which was developed in 1980 by Sony and Philips to standardize how information on a disk would be stored. The standard was printed in a red binder, hence its name. The encoding of an audio CD is best understood by tracing audio information through the encoding process.

0x08 graphic
 For sound to be “CD quality” it must be sampled at 44.1 kHz at 16 bits by two channels. This is a data rate of 1,411,200 bits/sec. 16 bits provides 65,536 (216) levels of sound information every 2.268x10-5 seconds. The audio data is broken into frames of 6 16bit words/channel. This data is then converted to 24 8 bit (1 byte) words. Each frame contains information for 1.36 ten thousandths of a second.

CD players uses Cross-Interleaved Reed-Solomon Coding, or CIRC. This begins by taking the 24 8 bit words in encoding them in a RS(28,24) code. With 4 parity check symbols, it is 2 error correcting. The data is then interleaved. This process distributes the information from this frame over 109 frames. This allows errors 0x08 graphic
on a large portion of the disk to be distributed over many small parts of the disk. This allows more errors to be corrected and prevents ruining an entire block of information. This is demonstrated in the following simplistic example:

Three length three code words must be transmitted, [010][001][011]. Allow the code to be 1 error correcting. If the information is not decoded successfully, something bad will happen. The data is interleaved by this pattern:

If the first word is incorrectly received as [110], when the information is de-interleaved, the received words would be [110][101][111]. Through error correction, the words would be decoded as [010][001][011]. If the data were not interleaved, it would have been corrupted and unreadable.

After interleaving, the data is encoded in a RS(32,28) code. This is also a 2 error correcting code. The data is once again interleaved with a new pattern. Interleaving works well for a CD because 1 frame is spread over 109 frames. Each frame is 32 bytes long. Each frame corrects up to 4 symbol errors. 109 frames can correct 436 errors. With interleaving, 13.625 frames can be corrected, where it would be impossible to do this without the interleaving.

The first code, RS(28,24) is called the C2 level of encoding. It corrects errors due to the physical condition of the CD and the way that the CD was recorded. The RS(32,28) code is the C1 level and it corrects errors due to fingerprints and scratches. This completes the encoding of the audio information, but control information must be added to the CD.

This is done by the addition of an 8 bit subcode to each frame. The subcode bits are designated P,Q,R,S,T,U,V,W. Only the P and Q bits are used on audio CDs. Bits R through W are used for CD-Graphics like karaoke CDs. The P bit is used to designate the start of a track. The Q bit provides timing information. The subcode bits from 98 frames are collected to form 8 98 bit words. Because the subcode is located with the music, the exact location and time on the disk is always known.

With the addition of a subcode block, the information is 33 bytes long. However, before it is encoded to the CD it must be modified for use on a CD. The information undergoes eight to fourteen modulation, or EFM. With this, each 8 bit word is assigned a 14 bit word from a ROM (read-only memory) dictionary. These words are designed to have a low number of transitions from 0's to 1's. Also, this increases the minimum distance of the code therefore adding an extra layer of error protection. Each 14 bit word is joined by 3 merging bits to aid in timing synchronization. Now the frame is 561 bits long. Each frame is assigned a unique 24 bit synchronization pattern to proceed it along with three merging bits. This makes one frame 588 bits long.

A block is made up of 98 frames. The rotational velocity of the CD changes so that the linear velocity over the laser is a consistent 1.3 m/s. At this rate, 75 blocks are read per second. 1 block with 98 frames with 24 sound data bytes at 8 bits each by 75 blocks per second is a data rate of 1,411,200 bits/second. This reproduces the original sound information rate. However, the actual data rate is 98 frames/block times 75 blocks/second by 488 bits/frame is 4,321,800 bits/second. CD-ROM format is slightly different in the amount of error correction it provides. The standard data rate for a CD-ROM is 150 kB/sec, or 1,233,600 bits/second.

The CIRC code used on audio CDs can correct burst errors of up to 3500 bits (2.4mm) and can interpolate error bursts of up to 12,000 bits (8.5 mm). Advances in technology in the past 20 years have lead to even more applications for CD technology including DVDs. The error correction on a CD guarantees that high quality music can be enjoyed consistently and reliably.

Bibliography

Coding and Modulation Schemes for Digital Audio

www.stanford.edu/courses/192b/lectures/5/5.html

 

Our Guide CD Recording Methods & Error Correction

www.a1-electronics.co.uk/PcHardware/CD-RW/RecordMethods.shtml

 

Frequently Asked Questions About Compact Discs

www.mscience.com/faq28.html

 

Compact Disc

www.cs.tut.fi/~ypsilon/80545/CD.html

 

Reed-Solomon Codes

www.4i2i.com/reed_solomon_codes.htm

 

Algebraic Decoding

math.berkeley.edu/~berlek/alg.html

 

Subcode On the Compact Disk

www.ee.washington.edu/conselec/CE/reports/Group.1/matt_page_individual/subcode.html

 

CD-ROM Technical Summary From Plastic Pits to "Fantasia" pauillac.inria.fr/~lang/hotlist/cdrom/Documents/tech-summary.html

 

CD Data Coding

www.disctronics.co.uk/technology/cdbasics/cd_frames.htm

 

CD Physical Specification

www.disctronics.co.uk/technology/cdbasics/cd_specs.htm

 

Compact Disc Creation Services CD-ROM Information

www.gi.alaska.edu/crc/cdrom/cdrom.html


[16b][16b] [8b][8b][8b][8b]

L [16b][16b] * [8b][8b][8b][8b]

[16b][16b] [8b][8b][8b][8b] *

*[24B](192 bits)

[16b][16b] [8b][8b][8b][8b] *

R [16b][16b] * [8b][8b][8b][8b]

[16b][16b] [8b][8b][8b][8b]

 

[0 1 0] [0 0 1] [0 1 1]

 

 

 

[0 0 0] [1 0 1] [1 1 1]


Wyszukiwarka

Podobne podstrony:
pieniadze nie sa wszystkim
dostalem wszystko
(1967) GDY WSZYSTKIE NARODY ZJEDNOCZĄ SIĘ POD POD KTRÓLESTWEM BOŻYMid 888
Identyfikacja Chrystusa we wszystkich wiekach 640409
Litania do Wszystkich Świętych Melodia II
Najpotężniejsza Nowenna z wszystkich nowenn do Opatrzności Bożej
MAS wszystkie pytania testowe 2007
Ze wszystkich kwiatków świata, dzień mamy i taty
WOJNA W AFRYCE POĄNOCNEJ, wszystko do szkoly
wszystkie wykłady z matmy stoiński - wersja na telefon, MATMA, matematyka
POPRAWA WSZYSTKICH KOLOKWIËW. 5fantastic.pl , Ćwiczenia
Pewnego razu wszystko zaczęło się od stworzenia świata, Filozofia

więcej podobnych podstron