143
правки
Изменения
Коды с коррекцией ошибок
|proof=TODO
}}
==Коды с коррекцией ошибок==
{{Определение
|definition=Кодом с коррекцией ошибок называется набор строк <tex>C \subset \Sigma^n</tex>, где <tex>\Sigma</tex> некоторый конечный алфавит. <tex>n</tex> называется размером блока, а <tex>log_{|\Sigma|}|C|</tex> уровнем кода. Расстоянием кода называется <tex>min_{x \neq y \in C} dist(x,y)</tex>, где <tex>dist(\cdot,\cdot)</tex> — расстояние Хэмминга.
}}
Взаимнооднознаячное отображение <tex>e:D \rightarrow \Sigma^n</tex> также иногда называют кодом с коррекцией ошибок. Его уровень и расстояние определяются как уровени и расстояние его образа <tex>e(D)</tex>.
Известно, что существуют семейства кодов <tex>\lbrace C_n \subset \lbrace 0,1 \rbrace^n \rbrace_{n \in \mathbb{N}}</tex>, для которых уровень и расстояние равны <tex>O(n)</tex> и существует схема полиномиального размера, проверяющая <tex>x \in C_n</tex>.
==Дополнительные материалы==
* [http://www.math.ias.edu/boaz/ExpanderCourse/|N. Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course, 2003].* [Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710–1722, 1996. Codes and complexity].
==Источники==
* [http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005].* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf|The PCP Theorem, Notes by Scott Alfeld, 2008].
