Forney algorithm - Revision history

Jennytallyho at 21:41, 15 March 2025

2025-03-15T21:41:22Z

← Previous revision		Revision as of 21:41, 15 March 2025
Line 1:		Line 1:
	In [[coding theory]], the '''Forney algorithm''' (or '''Forney's algorithm''') calculates the error values at known error locations. It is used as one of the steps in decoding [[BCH code]]s and [[Reed–Solomon error correction\|Reed–Solomon codes]] (a subclass of BCH codes). [[Dave Forney\|George David Forney Jr.]] developed the algorithm.<ref>{{Harvnb\|Forney\|1965}}</ref>		In [[coding theory]], the '''Forney algorithm''' (or '''Forney's algorithm''') calculates the error values at known error locations. It is used as one of the steps in decoding [[BCH code]]s and [[Reed–Solomon error correction\|Reed–Solomon codes]] (a subclass of BCH codes). [[Dave Forney\|George David Forney Jr.]] developed the algorithm in 1965.<ref>{{Harvnb\|Forney\|1965}}</ref>

	==Procedure==		==Procedure==

Beland: middot -> sdot per WP:⋅ (via WP:JWB)

2024-05-10T07:07:11Z

middot -> sdot per WP:⋅ (via WP:JWB)

← Previous revision		Revision as of 07:07, 10 May 2024
Line 46:		Line 46:
	<!-- nu is number of errors / order of Lambda(x). Better exposition needed. -->		<!-- nu is number of errors / order of Lambda(x). Better exposition needed. -->

	In the above expression, note that ''i'' is an integer, and λ<sub>''i''</sub> would be an element of the finite field. The operator &~~middot~~; represents ordinary multiplication (repeated addition in the finite field) which is the same as the finite field's multiplication operator, i.e.		In the above expression, note that ''i'' is an integer, and λ<sub>''i''</sub> would be an element of the finite field. The operator ⋅ represents ordinary multiplication (repeated addition in the finite field) which is the same as the finite field's multiplication operator, i.e.
	:<math>		:<math>
	i\lambda = (1+\ldots+1)\lambda=\lambda+\ldots+\lambda.		i\lambda = (1+\ldots+1)\lambda=\lambda+\ldots+\lambda.

2601:281:8200:ED70:0:0:0:D60C: /* Formal derivative */ There was some nonsense sentence I removed. Every ring with identity $R$ has a unique map $\mathbb{Z}\to R$ sending 1 to 1, i.e. integers make sense as ring elements in any ring. I think this would be better if the whole paragraph of exposition was removed (include what I wrote)..

2023-02-28T18:19:27Z

Formal derivative: There was some nonsense sentence I removed. Every ring with identity $R$ has a unique map $\mathbb{Z}\to R$ sending 1 to 1, i.e. integers make sense as ring elements in any ring. I think this would be better if the whole paragraph of exposition was removed (include what I wrote)..

← Previous revision		Revision as of 18:19, 28 February 2023
Line 46:		Line 46:
	<!-- nu is number of errors / order of Lambda(x). Better exposition needed. -->		<!-- nu is number of errors / order of Lambda(x). Better exposition needed. -->

	In the above expression, note that ''i'' is an integer, and λ<sub>''i''</sub> would be an element of the finite field. The operator · represents ordinary multiplication (repeated addition in the finite field) ~~and~~ ~~not~~ the finite field's multiplication operator.		In the above expression, note that ''i'' is an integer, and λ<sub>''i''</sub> would be an element of the finite field. The operator · represents ordinary multiplication (repeated addition in the finite field) which is the same as the finite field's multiplication operator, i.e.
			:<math>

			i\lambda = (1+\ldots+1)\lambda=\lambda+\ldots+\lambda.
			</math>
			For instance, in characteristic 2, <math>i\lambda=0, \lambda</math> according as ''i'' is even or odd.
	<!-- discuss simplification. When addition is exclusive or (common case), only odd ''i'' are relevant. -->		<!-- discuss simplification. When addition is exclusive or (common case), only odd ''i'' are relevant. -->

BattyBot: Removed non-content empty section(s), performed general fixes

2021-12-10T03:28:47Z

Removed non-content empty section(s), performed general fixes

← Previous revision		Revision as of 03:28, 10 December 2021
Line 95:		Line 95:
	}}		}}
	* [[W. Wesley Peterson]]'s book		* [[W. Wesley Peterson]]'s book

	==External links==

	{{DEFAULTSORT:Forney algorithm}}		{{DEFAULTSORT:Forney algorithm}}

Dicklyon: ce

2020-04-06T05:58:37Z

← Previous revision		Revision as of 05:58, 6 April 2020
Line 1:		Line 1:
	In [[coding theory]], the '''Forney algorithm''' (or '''Forney's algorithm''') calculates the error values at known error locations. It is used as one of the steps in decoding [[BCH code]]s and [[Reed–Solomon error correction\|Reed–Solomon codes]] (a subclass of BCH codes). [[Dave Forney\|George David Forney, Jr.]] developed the algorithm.<ref>{{Harvnb\|Forney\|1965}}</ref>		In [[coding theory]], the '''Forney algorithm''' (or '''Forney's algorithm''') calculates the error values at known error locations. It is used as one of the steps in decoding [[BCH code]]s and [[Reed–Solomon error correction\|Reed–Solomon codes]] (a subclass of BCH codes). [[Dave Forney\|George David Forney Jr.]] developed the algorithm.<ref>{{Harvnb\|Forney\|1965}}</ref>

	==Procedure==		==Procedure==
Line 70:		Line 70:
	{{reflist\|30em}}		{{reflist\|30em}}
	*{{Citation		*{{Citation
	\|first= G~~., Jr~~.		\|first= G.
	\|last= Forney		\|last= Forney
	\|authorlink=Dave Forney		\|authorlink=Dave Forney

Monkbot: /* References */Task 16: replaced (1×) / removed (0×) deprecated |dead-url= and |deadurl= with |url-status=;

2019-09-29T04:31:01Z

References: Task 16: replaced (1×) / removed (0×) deprecated |dead-url= and |deadurl= with |url-status=;

← Previous revision		Revision as of 04:31, 29 September 2019
Line 90:		Line 90:
	\|publisher = Stanford University		\|publisher = Stanford University
	\|url = http://www.stanford.edu/class/ee387/handouts/notes7.pdf		\|url = http://www.stanford.edu/class/ee387/handouts/notes7.pdf
	\|~~doi~~ =		\|url-status = dead
	\|deadurl = yes
	\|archiveurl = https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf		\|archiveurl = https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf
	\|archivedate = June 30, 2014		\|archivedate = June 30, 2014
	\|df =
	}}		}}
	* [[W. Wesley Peterson]]'s book		* [[W. Wesley Peterson]]'s book

InternetArchiveBot: Rescuing 1 sources and tagging 0 as dead. #IABot (v1.5.4)

2017-10-04T06:38:44Z

Rescuing 1 sources and tagging 0 as dead. #IABot (v1.5.4)

← Previous revision		Revision as of 06:38, 4 October 2017
Line 82:		Line 82:
	\|doi= 10.1109/TIT.1965.1053825}}		\|doi= 10.1109/TIT.1965.1053825}}
	*{{Citation		*{{Citation
	\|last=Gill		\|last = Gill
	\|first= John		\|first = John
	\|title= EE387 Notes #7, Handout #28		\|title = EE387 Notes #7, Handout #28
	\|date=n.d.		\|date = n.d.
	\|accessdate= April 21, 2010		\|accessdate = April 21, 2010
	\|pages=42–45		\|pages = 42–45
	\|publisher= Stanford University		\|publisher = Stanford University
	\|url= http://www.stanford.edu/class/ee387/handouts/notes7.pdf		\|url = http://www.stanford.edu/class/ee387/handouts/notes7.pdf
	\|doi=}}		\|doi =
			\|deadurl = yes
			\|archiveurl = https://web.archive.org/web/20140630172526/http://web.stanford.edu/class/ee387/handouts/notes7.pdf
			\|archivedate = June 30, 2014
			\|df =
			}}
	* [[W. Wesley Peterson]]'s book		* [[W. Wesley Peterson]]'s book

Glrx: /* References */ put Jr. on first=

2015-06-27T15:18:42Z

References: put Jr. on first=

← Previous revision		Revision as of 15:18, 27 June 2015
Line 70:		Line 70:
	{{reflist\|30em}}		{{reflist\|30em}}
	*{{Citation		*{{Citation
	\|first= G.		\|first= G., Jr.
	\|last= Forney~~, Jr.~~		\|last= Forney
	\|authorlink=Dave Forney		\|authorlink=Dave Forney
	\|title= On Decoding BCH Codes		\|title= On Decoding BCH Codes

Glrx: unknown to n.d.

2015-06-27T15:17:10Z

unknown to n.d.

← Previous revision		Revision as of 15:17, 27 June 2015
Line 8:		Line 8:
	Syndromes		Syndromes

	Error location polynomial<ref>{{Harvnb\|Gill\|~~unknown~~\|p=24}}</ref>		Error location polynomial<ref>{{Harvnb\|Gill\|n.d.\|p=24}}</ref>

	:<math>\Lambda(x) = \prod_{i=1}^\nu (1- x \, X_i) = 1 + \sum_{i=1}^\nu \lambda_i \, x^i</math>		:<math>\Lambda(x) = \prod_{i=1}^\nu (1- x \, X_i) = 1 + \sum_{i=1}^\nu \lambda_i \, x^i</math>
Line 22:		Line 22:
	:<math> \cdots \, </math>		:<math> \cdots \, </math>

	However, there is a more efficient method known as the Forney algorithm, which is based on [[Lagrange polynomial\|Lagrange interpolation]]. First calculate the error evaluator polynomial<ref name="Gill-Forney">{{Harvnb\|Gill\|~~unknown~~\|p=47}}</ref>		However, there is a more efficient method known as the Forney algorithm, which is based on [[Lagrange polynomial\|Lagrange interpolation]]. First calculate the error evaluator polynomial<ref name="Gill-Forney">{{Harvnb\|Gill\|n.d.\|p=47}}</ref>

	:<math>\Omega(x) = S(x)\,\Lambda(x) \pmod{x^{2t}} \, </math>		:<math>\Omega(x) = S(x)\,\Lambda(x) \pmod{x^{2t}} \, </math>
	<!-- previous used small omega; mod was x^(d-1); Gill uses 2t. -->		<!-- previous used small omega; mod was x^(d-1); Gill uses 2t. -->

	Where {{math\|''S''(''x'')}} is the partial syndrome polynomial:<ref>{{Harvtxt\|Gill\|~~unknown~~\|p=48}}</ref>		Where {{math\|''S''(''x'')}} is the partial syndrome polynomial:<ref>{{Harvtxt\|Gill\|n.d.\|p=48}}</ref>
	:<math>S(x) = s_0 x^0 + s_1 x^1 + s_2 x^2 + \cdots + s_{2t-1} x^{2t-1}.</math>		:<math>S(x) = s_0 x^0 + s_1 x^1 + s_2 x^2 + \cdots + s_{2t-1} x^{2t-1}.</math>

Glrx: /* References */ Gill n.d.

2015-06-27T15:16:07Z

References: Gill n.d.

← Previous revision		Revision as of 15:16, 27 June 2015
Line 85:		Line 85:
	\|first= John		\|first= John
	\|title= EE387 Notes #7, Handout #28		\|title= EE387 Notes #7, Handout #28
			\|date=n.d.
	\|accessdate= April 21, 2010		\|accessdate= April 21, 2010
	\|pages=42–45		\|pages=42–45