About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / DocBook / librs.tmpl




Custom Search

Based on kernel version 3.16. Page generated on 2014-08-06 21:38 EST.

1	<?xml version="1.0" encoding="UTF-8"?>
2	<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.1.2//EN"
3		"http://www.oasis-open.org/docbook/xml/4.1.2/docbookx.dtd" []>
4	
5	<book id="Reed-Solomon-Library-Guide">
6	 <bookinfo>
7	  <title>Reed-Solomon Library Programming Interface</title>
8	  
9	  <authorgroup>
10	   <author>
11	    <firstname>Thomas</firstname>
12	    <surname>Gleixner</surname>
13	    <affiliation>
14	     <address>
15	      <email>tglx@linutronix.de</email>
16	     </address>
17	    </affiliation>
18	   </author>
19	  </authorgroup>
20	
21	  <copyright>
22	   <year>2004</year>
23	   <holder>Thomas Gleixner</holder>
24	  </copyright>
25	
26	  <legalnotice>
27	   <para>
28	     This documentation is free software; you can redistribute
29	     it and/or modify it under the terms of the GNU General Public
30	     License version 2 as published by the Free Software Foundation.
31	   </para>
32	      
33	   <para>
34	     This program is distributed in the hope that it will be
35	     useful, but WITHOUT ANY WARRANTY; without even the implied
36	     warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
37	     See the GNU General Public License for more details.
38	   </para>
39	      
40	   <para>
41	     You should have received a copy of the GNU General Public
42	     License along with this program; if not, write to the Free
43	     Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
44	     MA 02111-1307 USA
45	   </para>
46	      
47	   <para>
48	     For more details see the file COPYING in the source
49	     distribution of Linux.
50	   </para>
51	  </legalnotice>
52	 </bookinfo>
53	
54	<toc></toc>
55	
56	  <chapter id="intro">
57	      <title>Introduction</title>
58	  <para>
59	  	The generic Reed-Solomon Library provides encoding, decoding
60		and error correction functions.
61	  </para>
62	  <para>
63	  	Reed-Solomon codes are used in communication and storage
64		applications to ensure data integrity. 
65	  </para>
66	  <para>
67	  	This documentation is provided for developers who want to utilize
68		the functions provided by the library.
69	  </para>
70	  </chapter>
71	  
72	  <chapter id="bugs">
73	     <title>Known Bugs And Assumptions</title>
74	  <para>
75		None.	
76	  </para>
77	  </chapter>
78	
79	  <chapter id="usage">
80	     	<title>Usage</title>
81		<para>
82			This chapter provides examples of how to use the library.
83		</para>
84		<sect1>
85			<title>Initializing</title>
86			<para>
87				The init function init_rs returns a pointer to an
88				rs decoder structure, which holds the necessary
89				information for encoding, decoding and error correction
90				with the given polynomial. It either uses an existing
91				matching decoder or creates a new one. On creation all
92				the lookup tables for fast en/decoding are created.
93				The function may take a while, so make sure not to 
94				call it in critical code paths.
95			</para>
96			<programlisting>
97	/* the Reed Solomon control structure */
98	static struct rs_control *rs_decoder;
99	
100	/* Symbolsize is 10 (bits)
101	 * Primitive polynomial is x^10+x^3+1
102	 * first consecutive root is 0
103	 * primitive element to generate roots = 1
104	 * generator polynomial degree (number of roots) = 6
105	 */
106	rs_decoder = init_rs (10, 0x409, 0, 1, 6);
107			</programlisting>
108		</sect1>
109		<sect1>
110			<title>Encoding</title>
111			<para>
112				The encoder calculates the Reed-Solomon code over
113				the given data length and stores the result in 
114				the parity buffer. Note that the parity buffer must
115				be initialized before calling the encoder.
116			</para>
117			<para>
118				The expanded data can be inverted on the fly by
119				providing a non-zero inversion mask. The expanded data is
120				XOR'ed with the mask. This is used e.g. for FLASH
121				ECC, where the all 0xFF is inverted to an all 0x00.
122				The Reed-Solomon code for all 0x00 is all 0x00. The
123				code is inverted before storing to FLASH so it is 0xFF
124				too. This prevents that reading from an erased FLASH
125				results in ECC errors.
126			</para>
127			<para>
128				The databytes are expanded to the given symbol size
129				on the fly. There is no support for encoding continuous
130				bitstreams with a symbol size != 8 at the moment. If
131				it is necessary it should be not a big deal to implement
132				such functionality.
133			</para>
134			<programlisting>
135	/* Parity buffer. Size = number of roots */
136	uint16_t par[6];
137	/* Initialize the parity buffer */
138	memset(par, 0, sizeof(par));
139	/* Encode 512 byte in data8. Store parity in buffer par */
140	encode_rs8 (rs_decoder, data8, 512, par, 0);
141			</programlisting>
142		</sect1>
143		<sect1>
144			<title>Decoding</title>
145			<para>
146				The decoder calculates the syndrome over
147				the given data length and the received parity symbols
148				and corrects errors in the data.
149			</para>
150			<para>
151				If a syndrome is available from a hardware decoder
152				then the syndrome calculation is skipped.
153			</para>
154			<para>
155				The correction of the data buffer can be suppressed
156				by providing a correction pattern buffer and an error
157				location buffer to the decoder. The decoder stores the
158				calculated error location and the correction bitmask
159				in the given buffers. This is useful for hardware
160				decoders which use a weird bit ordering scheme.
161			</para>
162			<para>
163				The databytes are expanded to the given symbol size
164				on the fly. There is no support for decoding continuous
165				bitstreams with a symbolsize != 8 at the moment. If
166				it is necessary it should be not a big deal to implement
167				such functionality.
168			</para>
169			
170			<sect2>
171			<title>
172				Decoding with syndrome calculation, direct data correction
173			</title>
174			<programlisting>
175	/* Parity buffer. Size = number of roots */
176	uint16_t par[6];
177	uint8_t  data[512];
178	int numerr;
179	/* Receive data */
180	.....
181	/* Receive parity */
182	.....
183	/* Decode 512 byte in data8.*/
184	numerr = decode_rs8 (rs_decoder, data8, par, 512, NULL, 0, NULL, 0, NULL);
185			</programlisting>
186			</sect2>
187	
188			<sect2>
189			<title>
190				Decoding with syndrome given by hardware decoder, direct data correction
191			</title>
192			<programlisting>
193	/* Parity buffer. Size = number of roots */
194	uint16_t par[6], syn[6];
195	uint8_t  data[512];
196	int numerr;
197	/* Receive data */
198	.....
199	/* Receive parity */
200	.....
201	/* Get syndrome from hardware decoder */
202	.....
203	/* Decode 512 byte in data8.*/
204	numerr = decode_rs8 (rs_decoder, data8, par, 512, syn, 0, NULL, 0, NULL);
205			</programlisting>
206			</sect2>
207	
208			<sect2>
209			<title>
210				Decoding with syndrome given by hardware decoder, no direct data correction.
211			</title>
212			<para>
213				Note: It's not necessary to give data and received parity to the decoder.
214			</para>
215			<programlisting>
216	/* Parity buffer. Size = number of roots */
217	uint16_t par[6], syn[6], corr[8];
218	uint8_t  data[512];
219	int numerr, errpos[8];
220	/* Receive data */
221	.....
222	/* Receive parity */
223	.....
224	/* Get syndrome from hardware decoder */
225	.....
226	/* Decode 512 byte in data8.*/
227	numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr);
228	for (i = 0; i &lt; numerr; i++) {
229		do_error_correction_in_your_buffer(errpos[i], corr[i]);
230	}
231			</programlisting>
232			</sect2>
233		</sect1>
234		<sect1>
235			<title>Cleanup</title>
236			<para>
237				The function free_rs frees the allocated resources,
238				if the caller is the last user of the decoder.
239			</para>
240			<programlisting>
241	/* Release resources */
242	free_rs(rs_decoder);
243			</programlisting>
244		</sect1>
245	
246	  </chapter>
247		
248	  <chapter id="structs">
249	     <title>Structures</title>
250	     <para>
251	     This chapter contains the autogenerated documentation of the structures which are
252	     used in the Reed-Solomon Library and are relevant for a developer.
253	     </para>
254	!Iinclude/linux/rslib.h
255	  </chapter>
256	
257	  <chapter id="pubfunctions">
258	     <title>Public Functions Provided</title>
259	     <para>
260	     This chapter contains the autogenerated documentation of the Reed-Solomon functions
261	     which are exported.
262	     </para>
263	!Elib/reed_solomon/reed_solomon.c
264	  </chapter>
265	  
266	  <chapter id="credits">
267	     <title>Credits</title>
268		<para>
269			The library code for encoding and decoding was written by Phil Karn.
270		</para>
271		<programlisting>
272			Copyright 2002, Phil Karn, KA9Q
273	 		May be used under the terms of the GNU General Public License (GPL)
274		</programlisting>
275		<para>
276			The wrapper functions and interfaces are written by Thomas Gleixner.
277		</para>
278		<para>
279			Many users have provided bugfixes, improvements and helping hands for testing.
280			Thanks a lot.
281		</para>
282		<para>
283			The following people have contributed to this document:
284		</para>
285		<para>
286			Thomas Gleixner<email>tglx@linutronix.de</email>
287		</para>
288	  </chapter>
289	</book>
Hide Line Numbers
About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Information is copyright its respective author. All material is available from the Linux Kernel Source distributed under a GPL License. This page is provided as a free service by mjmwired.net.