| dbo:abstract |
The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear-feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse. Reeds and Sloane offer an extension to handle a ring. Elwyn Berlekamp invented an algorithm for decoding Bose–Chaudhuri–Hocquenghem (BCH) codes. James Massey recognized its application to linear feedback shift registers and simplified the algorithm. Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm), but it is now known as the Berlekamp–Massey algorithm. (en) Der Berlekamp-Massey-Algorithmus dient dazu, das kürzeste, lineare rückgekoppelte Schieberegister zu finden, das eine gegebene Folge von Symbolen ausgibt. Die Symbole können aus einem beliebigen Körper stammen. Das Verfahren wurdevon 1968 bis 1969 von Elwyn Berlekamp und James Massey entwickelt. Anwendungen liegen im Bereich der effizienten Decodierung von BCH-Codes und Untergruppen wie den Reed-Solomon-Codes. (de) 벌러캠프-매시 알고리즘은 주어진 수열을 만들 수 있는 가장 작은 를 찾는 알고리즘이다. 다시 말해, 선형 점화식의 최소 다항식을 구하는 알고리즘이다. (ko) Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем. Алгоритм был открыт Элвином Берлекэмпом в 1968 году. Применение алгоритма к линейным кодам было найдено Джеймсом Мэсси в следующем году. Это стало ключом для практического применения кодов Рида — Соломона. (ru) 伯利坎普－梅西算法（英語：Berlekamp-Massey algorithm，简称B-M算法）用来构造一个尽可能短的线性反馈移位寄存器（linear feedback shift register，LFSR）来产生一个有限二元序列，同时，该算法也给出了的线性复杂度。该算法是一个多项式时间的迭代算法，以N长二元序列为输入，输出产生给序列式的最短LFSR的特征多项式及该LFSR的线性复杂度。 這一算法由埃爾溫·伯利坎普與發明。 (zh) |
| dbo:wikiPageExternalLink |
http://www.informationsuebertragung.ch/indexAlgorithmen.html https://berlekamp-massey-algorithm.appspot.com/ https://web.archive.org/web/20120716181541/http:/planetmath.org/encyclopedia/BerlekampMasseyAlgorithm.html https://code.google.com/p/lfsr/ |
| dbo:wikiPageID |
514832 (xsd:integer) |
| dbo:wikiPageLength |
8400 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1056438545 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Algorithm dbr:Decoding_methods dbc:Articles_with_example_code dbr:Elwyn_Berlekamp dbr:Reeds–Sloane_algorithm dbc:Cryptanalytic_algorithms dbr:BCH_code dbr:James_Massey dbr:Linear-feedback_shift_register dbr:Minimal_polynomial_(field_theory) dbr:Field_(mathematics) dbr:Recurrence_relation dbr:Ring_(mathematics) dbc:Error_detection_and_correction dbr:Reed–Solomon_error_correction dbr:PlanetMath dbr:Nonlinear-feedback_shift_register |
| dbp:id |
p/b120140 (en) |
| dbp:title |
Berlekamp-Massey algorithm (en) Berlekamp–Massey Algorithm (en) |
| dbp:urlname |
Berlekamp-MasseyAlgorithm (en) |
| dbp:wikiPageUsesTemplate |
dbt:Springer dbt:Distinguish dbt:Harvtxt dbt:In_lang dbt:MathWorld dbt:Reflist |
| dct:subject |
dbc:Articles_with_example_code dbc:Cryptanalytic_algorithms dbc:Error_detection_and_correction |
| gold:hypernym |
dbr:Algorithm |
| rdf:type |
owl:Thing dbo:Software yago:WikicatCryptanalyticAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment |
Der Berlekamp-Massey-Algorithmus dient dazu, das kürzeste, lineare rückgekoppelte Schieberegister zu finden, das eine gegebene Folge von Symbolen ausgibt. Die Symbole können aus einem beliebigen Körper stammen. Das Verfahren wurdevon 1968 bis 1969 von Elwyn Berlekamp und James Massey entwickelt. Anwendungen liegen im Bereich der effizienten Decodierung von BCH-Codes und Untergruppen wie den Reed-Solomon-Codes. (de) 벌러캠프-매시 알고리즘은 주어진 수열을 만들 수 있는 가장 작은 를 찾는 알고리즘이다. 다시 말해, 선형 점화식의 최소 다항식을 구하는 알고리즘이다. (ko) Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем. Алгоритм был открыт Элвином Берлекэмпом в 1968 году. Применение алгоритма к линейным кодам было найдено Джеймсом Мэсси в следующем году. Это стало ключом для практического применения кодов Рида — Соломона. (ru) 伯利坎普－梅西算法（英語：Berlekamp-Massey algorithm，简称B-M算法）用来构造一个尽可能短的线性反馈移位寄存器（linear feedback shift register，LFSR）来产生一个有限二元序列，同时，该算法也给出了的线性复杂度。该算法是一个多项式时间的迭代算法，以N长二元序列为输入，输出产生给序列式的最短LFSR的特征多项式及该LFSR的线性复杂度。 這一算法由埃爾溫·伯利坎普與發明。 (zh) The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear-feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse. Reeds and Sloane offer an extension to handle a ring. (en) |
| rdfs:label |
Berlekamp-Massey-Algorithmus (de) Berlekamp–Massey algorithm (en) 벌러캠프-매시 알고리즘 (ko) Алгоритм Берлекэмпа — Мэсси (ru) 伯利坎普－梅西算法 (zh) |
| owl:differentFrom |
dbr:Berlekamp's_algorithm |
| owl:sameAs |
freebase:Berlekamp–Massey algorithm wikidata:Berlekamp–Massey algorithm dbpedia-de:Berlekamp–Massey algorithm dbpedia-fa:Berlekamp–Massey algorithm dbpedia-ko:Berlekamp–Massey algorithm dbpedia-ru:Berlekamp–Massey algorithm dbpedia-tr:Berlekamp–Massey algorithm dbpedia-vi:Berlekamp–Massey algorithm dbpedia-zh:Berlekamp–Massey algorithm https://global.dbpedia.org/id/4yHF9 |
| prov:wasDerivedFrom |
wikipedia-en:Berlekamp–Massey_algorithm?oldid=1056438545&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Berlekamp–Massey_algorithm |
| is dbo:knownFor of |
dbr:Elwyn_Berlekamp |
| is dbo:wikiPageRedirects of |
dbr:Berlekamp-Massey_algorithm dbr:Berlekamp-Massey |
| is dbo:wikiPageWikiLink of |
dbr:List_of_algebraic_coding_theory_topics dbr:List_of_algorithms dbr:Index_of_cryptography_articles dbr:Rank_error-correcting_code dbr:Timeline_of_information_theory dbr:Elwyn_Berlekamp dbr:Reeds–Sloane_algorithm dbr:BCH_code dbr:James_Massey dbr:Linear-feedback_shift_register dbr:Euclidean_algorithm dbr:Berlekamp-Massey_algorithm dbr:History_of_information_theory dbr:Block_Wiedemann_algorithm dbr:Reed–Solomon_error_correction dbr:Berlekamp-Massey |
| is dbp:decoding of |
dbr:Rank_error-correcting_code dbr:Reed–Solomon_error_correction |
| is dbp:knownFor of |
dbr:Elwyn_Berlekamp |
| is foaf:primaryTopic of |
wikipedia-en:Berlekamp–Massey_algorithm |