Content deleted Content added
Added Template:Infobox code to the top of the article. |
|||
Line 1:
{{infobox code
| name = Expander codes
| image =
| image_caption =
| namesake =
| type = [[Linear block code]]
| block_length = <math>n</math>
| message_length = <math>n-m</math>
| rate = <math>1-m/n</math>
| distance = <math>2(1-\epsilon)\gamma\cdot n</math>
| alphabet_size = <math>2</math>
| notation = <math>[n,n-m,2(1-\epsilon)\gamma\cdot n]_2</math>-code
}}
In [[coding theory]], '''expander codes''' are a type of [[linear code]] which arises by using [[bipartite]] [[expander graph]]s. Along with [[concatenated codes]], expander codes are interesting since they can construct [[binary]] codes (codes using just 0 and 1) with constant positive [[rate]] and relative [[distance]]. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code. In fact, expander codes are the only known asymptotically good codes which can be both encoded and decoded from a constant fraction of errors in polynomial time.
| |||