Rank error-correcting code - Revision history

OAbot: Open access bot: doi added to citation with #oabot.

2023-08-12T19:03:41Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 19:03, 12 August 2023
Line 71:		Line 71:
	== Applications ==		== Applications ==
	There are several proposals for public-key cryptosystems based on rank codes. However, most of them have been proven insecure (see e.g. Journal of Cryptology,		There are several proposals for public-key cryptosystems based on rank codes. However, most of them have been proven insecure (see e.g. Journal of Cryptology,
	April 2008<ref>{{cite journal \| doi=10.1007/s00145-007-9003-9 \| volume=21 \| issue=2 \| title=Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes \| journal=Journal of Cryptology \| pages=280–301\|year = 2008\|last1 = Overbeck\|first1 = R.\| s2cid=2393853 }}</ref>).		April 2008<ref>{{cite journal \| doi=10.1007/s00145-007-9003-9 \| volume=21 \| issue=2 \| title=Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes \| journal=Journal of Cryptology \| pages=280–301\|year = 2008\|last1 = Overbeck\|first1 = R.\| s2cid=2393853 \| doi-access=free }}</ref>).

	Rank codes are also useful for error and erasure correction in [[network coding]].		Rank codes are also useful for error and erasure correction in [[network coding]].

Citation bot: Alter: title, template type. Add: s2cid, chapter, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1563/2384

2023-07-25T06:57:15Z

Alter: title, template type. Add: s2cid, chapter, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1563/2384

← Previous revision		Revision as of 06:57, 25 July 2023
Line 47:		Line 47:
	== Generating matrix ==		== Generating matrix ==
	There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.		There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.
	The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a '' Singleton system'') and later by Gabidulin <ref>{{ cite journal \| first=Ernst M. \| last=Gabidulin \| title=Theory of codes with maximum rank distance \| journal=Problems of Information Transmission \| volume=21 \| issue=1 \| year=1985 \| pages=1–12 \| url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=967&option_lang=eng }}</ref> (and Kshevetskiy <ref>{{ ~~cite~~ ~~journal~~ \| ~~first~~= Alexander \| ~~last~~= Kshevetskiy \| first2= Ernst M. \| last2= Gabidulin \| title=~~The new construction of rank~~ ~~codes \| journal=~~Proceedings ~~of IEEE~~ International Symposium on Information Theory (ISIT) 2005 \| date=4–9 September 2005 \| pages=2105–2108 \| isbn = 978-0-7803-9151-2 \| doi= 10.1109/ISIT.2005.1523717 }}</ref> ).		The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a '' Singleton system'') and later by Gabidulin <ref>{{ cite journal \| first=Ernst M. \| last=Gabidulin \| title=Theory of codes with maximum rank distance \| journal=Problems of Information Transmission \| volume=21 \| issue=1 \| year=1985 \| pages=1–12 \| url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=967&option_lang=eng }}</ref> (and Kshevetskiy <ref>{{ Cite book \| first1= Alexander \| last1= Kshevetskiy \| first2= Ernst M. \| last2= Gabidulin \| title= Proceedings. International Symposium on Information Theory, 2005. ISIT 2005 \| chapter= The new construction of rank codes \| date=4–9 September 2005 \| pages=2105–2108 \| isbn = 978-0-7803-9151-2 \| doi= 10.1109/ISIT.2005.1523717 \| s2cid= 11679865 }}</ref> ).

	Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as		Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as
Line 71:		Line 71:
	== Applications ==		== Applications ==
	There are several proposals for public-key cryptosystems based on rank codes. However, most of them have been proven insecure (see e.g. Journal of Cryptology,		There are several proposals for public-key cryptosystems based on rank codes. However, most of them have been proven insecure (see e.g. Journal of Cryptology,
	April 2008<ref>{{cite journal \| doi=10.1007/s00145-007-9003-9 \| volume=21 \| issue=2 \| title=Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes \| journal=Journal of Cryptology \| pages=280–301\|year = 2008\|last1 = Overbeck\|first1 = R.}}</ref>).		April 2008<ref>{{cite journal \| doi=10.1007/s00145-007-9003-9 \| volume=21 \| issue=2 \| title=Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes \| journal=Journal of Cryptology \| pages=280–301\|year = 2008\|last1 = Overbeck\|first1 = R.\| s2cid=2393853 }}</ref>).

	Rank codes are also useful for error and erasure correction in [[network coding]].		Rank codes are also useful for error and erasure correction in [[network coding]].
Line 96:		Line 96:
	\|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=967&option_lang=eng		\|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=967&option_lang=eng
	}}		}}
			*{{Cite book\|first1= Alexander
	*{{Citation
		⚫	\|last1= Kshevetskiy
	\|first= Alexander
⚫	\|~~last~~= Kshevetskiy
	\|first2= Ernst M.		\|first2= Ernst M.
	\|last2= Gabidulin		\|last2= Gabidulin
		⚫	\|title= Proceedings. International Symposium on Information Theory, 2005. ISIT 2005
	\|~~title~~=The new construction of rank codes		\|chapter= The new construction of rank codes
⚫	\|~~journal~~=Proceedings ~~of IEEE~~ International Symposium on Information Theory (ISIT) 2005
	\|date=4–9 September 2005		\|date=4–9 September 2005
	\|pages=2105–2108		\|pages=2105–2108
	\|isbn = 978-0-7803-9151-2		\|isbn = 978-0-7803-9151-2
	\|doi= 10.1109/ISIT.2005.1523717		\|doi= 10.1109/ISIT.2005.1523717
			\|s2cid= 11679865
	}}		}}
			*{{Cite book\|first1= Ernst M.
	*{{Citation
	\|~~first~~= ~~Ernst M.~~		\|last1= Gabidulin
	\|last= Gabidulin
	\|first2= Nina I.		\|first2= Nina I.
	\|last2= Pilipchuk		\|last2= Pilipchuk
		⚫	\|title= IEEE International Symposium on Information Theory, 2003. Proceedings.
	\|~~title~~=A new method of erasure correction by rank codes		\|chapter= A new method of erasure correction by rank codes
⚫	\|~~journal~~=~~Proceedings of the 2003~~ IEEE International Symposium on Information Theory
	\|date=June 29 – July 4, 2003		\|date=June 29 – July 4, 2003
	\|pages=423		\|pages=423
	\|isbn = 978-0-7803-7728-8		\|isbn = 978-0-7803-7728-8
	\|doi= 10.1109/ISIT.2003.1228440		\|doi= 10.1109/ISIT.2003.1228440
			\|s2cid= 122552232
	}}		}}

Erayatay: clarified what the sentence is actually intended to mean

2023-07-20T18:17:05Z

clarified what the sentence is actually intended to mean

← Previous revision		Revision as of 18:17, 20 July 2023
Line 43:		Line 43:

	==Rank code==		==Rank code==
	A set <math>\{x_1, x_2, \dots, x_n\}</math> of vectors from <math>X^n</math> is called a code with code distance <math>d = \min d\left( x_i ,x_j \right)</math>. If the set also forms a ''k''-dimensional subspace of <math>X^n</math>, then it is called a linear (''n'', ''k'')-code with distance <math>d</math>. Such a linear rank metric code always satisfies the Singleton bound <math>d \leq n - k + 1</math>.		A set <math>\{x_1, x_2, \dots, x_n\}</math> of vectors from <math>X^n</math> is called a code with code distance <math>d = \min d\left( x_i ,x_j \right)</math>. If the set also forms a ''k''-dimensional subspace of <math>X^n</math>, then it is called a linear (''n'', ''k'')-code with distance <math>d</math>. Such a linear rank metric code always satisfies the Singleton bound <math>d \leq n - k + 1</math> with equality.

	== Generating matrix ==		== Generating matrix ==

71.187.223.181 at 22:07, 6 October 2021

2021-10-06T22:07:09Z

← Previous revision		Revision as of 22:07, 6 October 2021
Line 47:		Line 47:
	== Generating matrix ==		== Generating matrix ==
	There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.		There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.
	The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a '' Singleton system'') and later by Gabidulin, and ~~extended~~ by Kshevetskiy ~~and~~ Gabidulin.		The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a '' Singleton system'') and later by Gabidulin <ref>{{ cite journal \| first=Ernst M. \| last=Gabidulin \| title=Theory of codes with maximum rank distance \| journal=Problems of Information Transmission \| volume=21 \| issue=1 \| year=1985 \| pages=1–12 \| url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=967&option_lang=eng }}</ref> (and Kshevetskiy <ref>{{ cite journal \| first= Alexander \| last= Kshevetskiy \| first2= Ernst M. \| last2= Gabidulin \| title=The new construction of rank codes \| journal=Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005 \| date=4–9 September 2005 \| pages=2105–2108 \| isbn = 978-0-7803-9151-2 \| doi= 10.1109/ISIT.2005.1523717 }}</ref> ).

	Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as		Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as

71.187.223.181 at 21:51, 6 October 2021

2021-10-06T21:51:56Z

← Previous revision		Revision as of 21:51, 6 October 2021
Line 47:		Line 47:
	== Generating matrix ==		== Generating matrix ==
	There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.		There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.
	The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a '' Singleton system'') and later by (Kshevetskiy and) Gabidulin.		The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a '' Singleton system'') and later by Gabidulin, and extended by Kshevetskiy and Gabidulin.

	Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as		Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as

37.194.2.245: /* Generating matrix */

2021-09-20T10:55:38Z

Generating matrix

← Previous revision		Revision as of 10:55, 20 September 2021
Line 63:		Line 63:
	g_1^{[2 m]} & g_2^{[2 m]} & \dots & g_n^{[2 m]} \\		g_1^{[2 m]} & g_2^{[2 m]} & \dots & g_n^{[2 m]} \\
	\dots & \dots & \dots & \dots \\		\dots & \dots & \dots & \dots \\
	g_1^{[k m]} & g_2^{[k m]} & \dots & g_n^{[k m]}		g_1^{[(k-1) m]} & g_2^{[(k-1) m]} & \dots & g_n^{[(k-1) m]}
	\end{array}} \right\\|,		\end{array}} \right\\|,
	</math>		</math>

Charc2018: #suggestededit-add 1.0

2021-09-02T17:56:34Z

#suggestededit-add 1.0

← Previous revision		Revision as of 17:56, 2 September 2021
Line 1:		Line 1:
	{{infobox code		{{Short description\|Error-correcting code}}{{infobox code
	\| name = Rank codes		\| name = Rank codes
	\| image =		\| image =

Citation bot: Add: doi, date. Removed URL that duplicated unique identifier. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | via #UCB_toolbar

2020-02-28T18:15:53Z

Add: doi, date. Removed URL that duplicated unique identifier. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | via #UCB_toolbar

← Previous revision		Revision as of 18:15, 28 February 2020
Line 103:		Line 103:
	\|title=The new construction of rank codes		\|title=The new construction of rank codes
	\|journal=Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005		\|journal=Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005
	\|~~year~~=4–9 September 2005		\|date=4–9 September 2005
	\|pages=2105–2108		\|pages=2105–2108
	\|isbn = 978-0-7803-9151-2		\|isbn = 978-0-7803-9151-2
	\|~~url~~=~~https:~~/~~/ieeexplore~~.~~ieee~~.~~org/document/~~1523717		\|doi= 10.1109/ISIT.2005.1523717
	}}		}}
	*{{Citation		*{{Citation
	\|first= Ernst M.		\|first= Ernst M.
Line 118:		Line 118:
	\|pages=423		\|pages=423
	\|isbn = 978-0-7803-7728-8		\|isbn = 978-0-7803-7728-8
	\|~~url~~=~~https:~~/~~/ieeexplore~~.~~ieee~~.~~org/document/~~1228440		\|doi= 10.1109/ISIT.2003.1228440
	}}		}}

	==External links==		==External links==

Citation bot: Alter: url. | You can use this bot yourself. Report bugs here.| Activated by User:Nemo bis | via #UCB_webform

2019-12-04T09:39:04Z

Alter: url. | You can use this bot yourself. Report bugs here.| Activated by User:Nemo bis | via #UCB_webform

← Previous revision		Revision as of 09:39, 4 December 2019
Line 106:		Line 106:
	\|pages=2105–2108		\|pages=2105–2108
	\|isbn = 978-0-7803-9151-2		\|isbn = 978-0-7803-9151-2
	\|url=~~http~~://ieeexplore.ieee.org/~~xpl~~/~~freeabs_all.jsp?arnumber=~~1523717		\|url=https://ieeexplore.ieee.org/document/1523717
	}}		}}
	*{{Citation		*{{Citation
Line 118:		Line 118:
	\|pages=423		\|pages=423
	\|isbn = 978-0-7803-7728-8		\|isbn = 978-0-7803-7728-8
	\|url=~~http~~://ieeexplore.ieee.org/~~xpl~~/~~freeabs_all.jsp?arnumber=~~1228440		\|url=https://ieeexplore.ieee.org/document/1228440
	}}		}}

2A02:AB88:38C2:6D00:BDC5:906D:8071:10DD: /* Generating matrix */

2019-09-04T22:05:04Z

Generating matrix

← Previous revision		Revision as of 22:05, 4 September 2019
Line 47:		Line 47:
	== Generating matrix ==		== Generating matrix ==
	There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.		There are several known constructions of rank codes, which are ''maximum rank distance'' (or MRD) codes with ''d'' = ''n'' − ''k'' + 1.
	The easiest one is known as the (generalized) Gabidulin code, discovered first by Delsarte and later by (Kshevetskiy and) Gabidulin.		The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a '' Singleton system'') and later by (Kshevetskiy and) Gabidulin.

	Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as		Let's define a Frobenius power <math>[i]</math> of the element <math>x \in GF(q^N)</math> as