0
$\begingroup$

In an example I read in technical paper that used ReedSolmon Codes. I encountered the following statement:

Using an outer RS(224,208) reed solomon block code and if the length of data TO BE encoded is $x$ octets then the RESULTING total number of Reed Solomon codeword after encoding is

$$N=\lceil\frac{x}{208} \rceil$$

the claim continues with the following

the total number of RS encoded symbols is given by

$$x+ N *16$$

I don't understand, shouldnt the number of codewords be $$N= \lceil \frac{x\times 8}{208}\rceil$$

and the second statement, in general what does encoded symbols mean?

Any reference are highly appreciated.

$\endgroup$
1
  • $\begingroup$ Instead of octets I might talk about bytes. Anyway, your data consists of $x$ octets/bytes, and a single codeword of this RS-code has a payload of 208 octets/bytes. May be your confusion comes from forgetting that RS-codes (of this length) operate on bytes instead of bits? $\endgroup$ – Jyrki Lahtonen Jun 18 '15 at 7:30
2
$\begingroup$

Each 3-bit octet is embedded into an 8-bit byte that is a symbol in GF$(2^8)$, the binary field with $2^8$ elements. So, if there are $x$ octets, we have $x$ bytes, which we group into sets of $208$ data bytes, and append $16$ parity bites to each set of $208$ to make a Reed-Solomon codeword of $224$ symbols. How many such codewords do we have? Well, the number is obviously $$N = \left\lceil\frac{x}{208}\right\rceil$$ with $\left\lfloor\frac{x}{208}\right\rfloor$ codewords having a full set of $208$ data symbols and possibly one codeword having $x - 208\cdot \left\lfloor\frac{x}{208}\right\rfloor$ data symbols. So, how many symbols in all codewords? Well, each of the $N$ codewords has $16$ parity symbols and so the total number of codeword symbols is $16N$ parity symbols plus $x$ data symbols for the claimed total of $x+16N$ symbols. There is one caveat, though. The one codeword that has $x - 208\cdot \left\lfloor\frac{x}{208}\right\rfloor$ data symbols and $16$ parity symbols is a shortened codeword: we are assuming that the leading $208 - \left(x - 208\cdot \left\lfloor\frac{x}{208}\right\rfloor\right)$ data symbols are identically $0$ and thus need not be transmitted at all. This is fine as long as the decoder knows (i) that the "last"codeword is a shortened codeword, and (ii) knows how to handle such shortened codewords. In fact, even the encoder needs to know that the "last" set of data bytes is a few bytes short of a load and create the shortened codeword accordingly.

$\endgroup$
1
  • $\begingroup$ thank you for explanation and remark $\endgroup$ – Henry Jun 24 '15 at 14:49
1
$\begingroup$

You have your data split into $N$ groups of 208 octets. Each of these groups gets 16 octets appended to it as parity symbols to make 224 symbols in each complete group (codeword).

"Encoded symbols" must refer to the symbols that the RS encoded codeword is made of, there are 224 of these in a codeword.

$\endgroup$
0
$\begingroup$

Applications[edit]

1) Data storage: Reed–Solomon coding is very widely used in mass storage systems to correct the burst errors associated with media defects.

Reed–Solomon coding is a key component of the compact disc. It was the first use of strong error correction coding in a mass-produced consumer product, and DAT and DVD use similar schemes. In the CD, two layers of Reed–Solomon coding separated by a 28-way convolutional interleaver yields a scheme called Cross-Interleaved Reed–Solomon Coding (CIRC). The first element of a CIRC decoder is a relatively weak inner (32,28) Reed–Solomon code, shortened from a (255,251) code with 8-bit symbols. This code can correct up to 2 byte errors per 32-byte block. More importantly, it flags as erasures any uncorrectable blocks, i.e., blocks with more than 2 byte errors. The decoded 28-byte blocks, with erasure indications, are then spread by the deinterleaver to different blocks of the (28,24) outer code. Thanks to the deinterleaving, an erased 28-byte block from the inner code becomes a single erased byte in each of 28 outer code blocks. The outer code easily corrects this, since it can handle up to 4 such erasures per block.

The result is a CIRC that can completely correct error bursts up to 4000 bits, or about 2.5 mm on the disc surface. This code is so strong that most CD playback errors are almost certainly caused by tracking errors that cause the laser to jump track, not by uncorrectable error bursts.[5]

DVDs use a similar scheme, but with much larger blocks, a (208,192) inner code, and a (182,172) outer code.

Reed–Solomon error correction is also used in parchive files which are commonly posted accompanying multimedia files on USENET. The Distributed online storage service Wuala (discontinued in 2015) also used to make use of Reed–Solomon when breaking up files.

2) Bar code: Almost all two-dimensional bar codes such as PDF-417, MaxiCode, Datamatrix, QR Code, and Aztec Code use Reed–Solomon error correction to allow correct reading even if a portion of the bar code is damaged. When the bar code scanner cannot recognize a bar code symbol, it will treat it as an erasure.

Reed–Solomon coding is less common in one-dimensional bar codes, but is used by the PostBar symbology.

3) Data transmission: Specialized forms of Reed–Solomon codes, specifically Cauchy-RS and Vandermonde-RS, can be used to overcome the unreliable nature of data transmission over erasure channels. The encoding process assumes a code of RS(N, K) which results in N codewords of length N symbols each storing K symbols of data, being generated, that are then sent over an erasure channel.

Any combination of K codewords received at the other end is enough to reconstruct all of the N codewords. The code rate is generally set to 1/2 unless the channel's erasure likelihood can be adequately modelled and is seen to be less. In conclusion, N is usually 2K, meaning that at least half of all the codewords sent must be received in order to reconstruct all of the codewords sent.

Reed–Solomon codes are also used in xDSL systems and CCSDS's Space Communications Protocol Specifications as a form of forward error correction.

4)Space transmission: One significant application of Reed–Solomon coding was to encode the digital pictures sent back by the Voyager space probe.

Voyager introduced Reed–Solomon coding concatenated with convolutional codes, a practice that has since become very widespread in deep space and satellite (e.g., direct digital broadcasting) communications.

Viterbi decoders tend to produce errors in short bursts. Correcting these burst errors is a job best done by short or simplified Reed–Solomon codes.

Modern versions of concatenated Reed–Solomon/Viterbi-decoded convolutional coding were and are used on the Mars Pathfinder, Galileo, Mars Exploration Rover and Cassini missions, where they perform within about 1–1.5 dB of the ultimate limit, being the Shannon capacity.

These concatenated codes are now being replaced by more powerful turbo codes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.