Content deleted Content added
rvv |
Added the two main types of encoding. Kept technical level to lay-person with real world examples |
||
Line 1:
'''Coding theory''' deals with the properties of [[code]]s and thus with their fitness for a specific application.
There are two classes of codes. The first is Source Encoding which attempts to compress the data from a source in order to transmit it more efficiently. We see this in practice every day on the Internet where the commom "Zip" data compression is used to reduce the network load and make files smaller. The second is Channel Encoding. This technique adds extra data bits, commonly called parity bits, to make the tranmission of data more robust to disturbances present on the transmission channel. There are many application that the ordinary user is not aware of that utilize channel encoding. A typical music CD has powerful BCH block codes to correct for scratches and dust. In this application the transmission channel is the CD itself. Cell phones also use powerful coding techniquie 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.
The aim of source encoding is to take the source data and make it smaller. FAX transmission which has been around for many years uses a simple run length code. The principle is to recognize that most documents are white space with brief interruptions for the black typing. So FAX compresses a document by adding a repeat count to the next transisition. It may tell the receiver that 100 of the next pixels are white. Another common encoding technique is string compression. This is used for data files. The encoder has a dictionary of strings. It matches the incoming text to the strings in the dictionary and when found, it will send a single number to the receiver which is the index to the string. All know implementations of string compression are adaptive in nature and allow the encoder to create new strings and transmit them to the decoder so the two dictionaries remain the same.
The aim of channel encoding theory is to find codes which transmit quickly, contain many valid [[code word]]s and can correct or at least [[error detection|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 repitions bit by bit and take a majortiy 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.
Other codes are more appropiate for different applications. Deep space communications are limited by the thermal noise of the receiver which is more of a continous 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 continous 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.
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.
Line 9 ⟶ 15:
* the minimum [[Hamming distance]] between two valid code words
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 coded we see every day on our cell phones. These are the Code Division Multiple Acess (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 properities 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".
== See also ==
| |||