Generalized minimum-distance decoding: Difference between revisions

Revision as of 12:09, 30 October 2011

Revision as of 04:45, 31 October 2011

Line 113:

Every loop of 1~4 can be run in [[polynomial time]], the algorithm above can also be computed in polynomial time.

Specifically, each call to an errors and erasures decoder of < <math><dD/2</math> errors takes <math>O(d)</math> time. Finally, the runtime of the algorithm above is <math>O(NQn^{O(1)} + NT_\text{out})</math> where <math>T_\text{out}</math> is the running time of the outer errors and erasures decoder.

==See also==