FACTOID # 12: It's not the government they hate: Washington DC has the highest number of hate crimes per capita in the US.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Coding theory

Coding theory is a branch of mathematics and computer science dealing with the error-prone process of transmitting data across noisy channels, via clever means, so that a large number of errors that occur can be corrected. It also deals with the properties of codes, and thus with their fitness for a specific application. Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In information theory, the noisy-channel coding theorem establishes that however contaminated with noise interference a communication channel may be, it is possible to communicate digital data (information) error-free up to a given maximum rate through the channel. ... In communications, a code is a rule for converting a piece of information (for example, a letter, word, or phrase) into another form or representation, not necessarily of the same type. ...


There are two classes of codes.

  1. Source coding (Entropy encoding)
  2. Channel coding (Forward error correction)

The first, source encoding, attempts to compress the data from a source in order to transmit it more efficiently. We see this practice every day on the Internet where the common "Zip" data compression is used to reduce the network load and make files smaller. The second, channel encoding adds extra data bits, commonly called parity bits, to make the tranmission of data more robust to disturbances present on the transmission channel. The ordinary user may not be aware of many applications using channel coding. A typical music CD uses a powerful Reed-Solomon code to correct for scratches and dust. In this application the transmission channel is the CD itself. Cell phones also use powerful coding technique to correct for the fading and noise of high frequency radio transmission. Data modems, telephone transmission and of course NASA all employ powerful channel coding to get the bits through. An entropy encoding is a coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ... It has been suggested that this article or section be merged with Error correction and detection. ... Reed-Solomon error correction is a coding scheme which works by first constructing a polynomial from the data symbols to be transmitted and then sending an over-sampled plot of the polynomial instead of the original symbols themselves. ...

Contents


Source Coding

The aim of source coding is to take the source data and make it smaller. An indepth article can be found at Source coding. In computer science, data compression or source coding is the process of encoding information using fewer bits, or information units, thanks to specific encoding schemes. ...


Principle

Entropy of a source is the measure of information. Basically source codes try to reduce the redundancy present in the source, and represent the source with a fewer bits that carry more information.


Various techniques used by source coding schemes try to achieve the limit of Entropy of the source. C(x) ge H(x), where H(x) is entropy of source (bitrate), and C(x) is the bitrate after compression. In particular, no source coding scheme can be better than the entropy limit of the symbol.


Example

Facsimilie transmission uses a simple run length code. Fax (short for facsimile - from Latin fac simile, make similar, i. ... RLE could be Run-length encoding Real life experience This is a disambiguation page — a navigational aid which lists other pages that might otherwise share the same title. ...


Channel encoding

The aim of channel encoding theory is to find codes which transmit quickly, contain many valid code words and can correct or at least detect many errors. These aims are mutually exclusive however, so different codes are optimal for different applications. The needed properties of this code mainly depend on the probability of errors happening during transmission. In a typical CD, the impairment is mainly dust or scratches. Thus codes are used in an interleaved manner. The data is spread out over the disk. Although not a very good code, a simple repeat code can serve as an understandable example. Suppose we take a block of data bits (representing sound) and send it three times. At the receiver we will examine the three repetitions bit by bit and take a majority vote. The twist on this is that we don't merely send the bits in order. We interleave them. The block of data bits is first divided into 4 smaller blocks. Then we cycle through the block and send one bit from the first, then the second, etc. This is done three times to spread the data out over the surface of the disk. In the context of the simple repeat code, this may not appear effective. However, there are more powerful codes known which are very effective at correcting the "burst" error of a scratch or a dust spot when this interleaving technique is used. A Code word may refer any of several concepts: For telecommunications senses, see Code word (telecommunication). ... In computer science and information theory, error correction consists of using methods to detect and/or correct errors in the transmission or storage of data by the use of some amount of redundant data and (in the case of transmission) the selective retransmission of incorrect segments of the data. ...


Other codes are more appropriate for different applications. Deep space communications are limited by the thermal noise of the receiver which is more of a continuous nature than a bursty nature. Likewise, narrowband modems are limited by the noise present in the telephone network and is also modeled better as a continuous disturbance. Cell phones are troubled by rapid fading. The high frequencies used can cause rapid fading of the signal even if the receiver is moved a few inches. Again there are a class of channel codes that are designed to combat fading. Johnson-Nyquist noise (sometimes thermal noise, Johnson noise or Nyquist noise) is the noise generated by the equilibrium fluctuations of the electric current inside an electrical conductor, which happens without any applied voltage, due to the random thermal motion of the charge carriers (the electrons). ...


The term algebraic coding theory denotes the sub-field of coding theory where the properties of codes are expressed in algebraic terms and then further researched.


Algebraic Coding theory, is basically divided into two major types of codes

  1. Linear block codes
  2. Convolutional codes

It analyzes the following three properties of a code -- mainly:

  • code word length
  • total number of valid code words
  • the minimum Hamming distance between two valid code words

In information theory, the Hamming distance, named after Richard Hamming, is the number of positions in two strings of equal length for which the corresponding elements are different. ...

Linear block codes

Linear block codes, have the property of linearity, i.e the sum of any two codewords is also a code word; and they are applied to the source bits in blocks; hence the name linear block codes. There are block codes that are not linear, but it is difficult to prove that a code is a good one without this property. The word linear comes from the Latin word linearis, which means created by lines. ...


Any linear block code is represented as (n,m,dmin) where

  1. n , is the length of the codeword, in symbols,
  2. m , is the number of source symbols that will be used for encoding at once,
  3. dmin, is the minimum hamming distance for the code

There are many types within linear block codes, like

  1. Cyclic codes (Hamming code, is a subset of cyclic codes)
  2. Repetition codes
  3. Parity codes
  4. Reed Solomon codes
  5. BCH code
  6. Reed Muller codes
  7. Perfect codes

Block codes are tied to the "penny packing" problem which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful Golay code used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is) the dimensions refer to the length of the codeword as defined above. Let C be a linear code over a finite field A of block length n. ... In telecommunication, a Hamming code is an error-correcting code named after its inventor, Richard Hamming. ... Repetition code is a coding scheme that repeats the bits across a channel to achieve error free communication. ... Reed-Solomon error correction is a coding scheme which works by first constructing a polynomial from the data symbols to be transmitted and then sending an over-sampled plot of the polynomial instead of the original symbols themselves. ... A BCH (Bose, Ray-Chaudhuri, Hocquenghem) code is a much studied code within the study of coding theory and more specifically error-correcting codes. ... The Reed-Muller codes are a family of linear error-correcting codes used in communications. ... The Hamming bound is a bound on the parameters of a (not necessarily linear) code . ...


The theory of coding uses the N-dimensional sphere model. For example, how many pennies can be packed into a circle on a tabletop or in 3 dimensions, how many marbles can be packed into a globe. Other considerations enter the choice of a code. For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners. As the dimensions get larger, the percentage of empty space grows smaller. But at certain dimensions, the packing uses all the space and these codes are the so called perfect codes. There are very few of these codes (Hamming [n,k,3], Golay [24,12,8],[23,12,7],[12,6,6])


Another item which is often overlooked is the number of neighbors a single codeword may have. Again, lets use pennies as an example. First we pack the pennies in a rectangular grid. Each penny will have 4 near neighbors (and 4 at the corners which are farther away). In a hexagon, each penny will have 6 near neighbors. When we increase the dimensions, the number of near neighbors increases very rapidly.


The result is the number of ways for noise to make the receiver choose a neighbor (hence an error) grows as well. This is a fundamental limitation of block codes, and indeed all codes. It may be harder to cause an error to a single neighbor, but the number of neighbors can be large enough so the total error probability actually suffers.


Convolution codes

Convolutional codes are used in voiceband modems (V.32, V.17, V.34) and in GSM mobile phones, as well as satellite and military communication devices.


Here the idea is to make every codeword symbol be the weighted sum of the various input message symbols. This is like convolution used in LTI systems to find the output of a system, when you know the input and impulse response. In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. ... In electrical engineering, specifically in signal processing and control theory, LTI system theory investigates the response of a linear, time-invariant system to an arbitrary input signal. ...


So we generally find the output of the system [convolutional encoder] , which is the convolution of the input bit, against the states of the convolution encoder, registers.


Fundamentally, convolutional codes do not offer more protection against noise than an equivalent block code. In many cases, they generally offer greater simplicity of implementation over a block code of equal power. The encoder is usually a simple circuit which has state memory and some feedback logic, normally XOR gates. The decoder can be implemented in software or firmware.


The Viterbi algorithm is the optimum algorithm used to decode convolutional codes. There are simplifications to reduce the computational load. They rely on searching only the most likely paths. Although not optimum, they have generally found to give good results in the lower noise environments. Modern microprocessors are capable of implementing these reduced search algorithms at rate greater than 4000 codewords/s. The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ...


Applications of coding theory

Another concern of coding theory is designing codes that help synchronization. A code may be designed so that a phase shift can be easily detected and corrected and that multiple signals can be sent on the same channel. There is an interesting class of codes we see every day on our cell phones. These are the Code Division Multiple Access (CDMA) codes. The details are beyond the scope of this discussion but briefly, each phone is assigned a codeword from a special class (algebraic field). When transmitting, the code word is used to scramble the bits representing the voice message. At the receiver, a descrambling process is done to decipher the message. The properties of this class of code words allow many users (with different codes) to use the same radio channel at the same time. The receiver, using the descrambling, will only "hear" other callers as low level "noise". To meet Wikipedias quality standards, this article or section may require cleanup. ... Waves with the same phase Waves with different phases The phase of a wave relates the position of a feature, typically a peak or a trough of the waveform, to that same feature in another part of the waveform (or, which amounts to the same, on a second waveform). ... This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ...


Another popular class of codes are the Automatic Repeat reQuest (ARQ) codes. In this general class, the transmitter adds the parity check bits to a longer message. The receiver checks the parity bits against the message and if there is not a match, it will ask the transmitter to retransmit the message. Almost all wide area networks and protocols except for the very simple ones use ARQ retransmission. Common protocols include SDLC (IBM), TCP (Internet), X.25 (International) and many others. There is an extensive field of research on this topic because of the problem of matching a rejected packet against a new packet. Is it a new one or is it a retransmission? Typically numbering schemes have been used, although in some networks, the packet may have another identifier or it may be left to higher layers to request retransmission. TCP/IP is a good example of a protocol that supports both techniques. In a connected scenario, TCP/IP leaves the retransmission to the network thus it uses the ARQ coding. In a connectionless network, ARQ is not used. Instead, it is up to the application to examine the packet and request retransmission as needed. This may go as high up as requiring the user to hit the "refresh" button on a browser. But, even this is still in the class of ARQ research; the user just has to become involved. ARQ is an acronym for: Automatic Repeat-reQuest. ... Wan is a Chinese abbreviation for the province of Anhui in China. ... SDLC can refer to: Synchronous Data Link Control System Design Life Cycle (or System Development Life Cycle) This is a disambiguation page — a navigational aid which lists other pages that might otherwise share the same title. ... The Transmission Control Protocol (TCP) is one of the core protocols of the Internet protocol suite. ... X.25 is an ITU-T standard protocol suite for WAN networks using the phone or ISDN system as the networking hardware. ... The Internet protocol suite is the set of communications protocols that implement the protocol stack on which the Internet runs. ...


See also


  Results from FactBites:
 
Coding theory: the first 50 years (1013 words)
Coding theory is the branch of mathematics concerned with transmitting data across noisy channels and recovering the message.
His first attempt produced a code in which four data bits were followed by three check bits which allowed not only the detection but the correction of a single error.
The value of error-correcting codes for information transmission, both on Earth and from space, was immediately apparent, and a wide variety of codes were constructed which achieved both economy of transmission and error-correction capacity.
Coding theory - Wikipedia, the free encyclopedia (1757 words)
Coding theory is a branch of mathematics and computer science dealing with the error-prone process of transmitting data across noisy channels, via clever means, so that a large number of errors that occur can be corrected.
Cyclic codes (Hamming code, is a subset of cyclic codes)
The Viterbi algorithm is the optimum algorithm used to decode convolutional codes.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m