[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2en\/wiki14\/singleton-barrier-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2en\/wiki14\/singleton-barrier-wikipedia\/","headline":"Singleton barrier-Wikipedia","name":"Singleton barrier-Wikipedia","description":"before-content-x4 The Singleton barrier describes an upper barrier for the minimum distance d {displaystyle d} after-content-x4 of a block code","datePublished":"2020-04-28","dateModified":"2020-04-28","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2en\/wiki14\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2en\/wiki14\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e85ff03cbe0c7341af6b982e47e9f90d235c66ab","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e85ff03cbe0c7341af6b982e47e9f90d235c66ab","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/all2en\/wiki14\/singleton-barrier-wikipedia\/","wordCount":6232,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4The Singleton barrier describes an upper barrier for the minimum distance d {displaystyle d}        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4of a block code of the length n {displaystyle n} for information words of the length k {displaystyle k} About a uniform alphabet        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4A {displaystyle Sigma } . It is: d \u2264 n – k + first {displaystyle dleq n-k+1} The barrier can be intuitively cleared in the following way:        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Acceptance: alphabet A = { 0 , … , q – first } {displaystyle Sigma ={0,ldots ,q-1}} Number of possible information words: |I|= qk{displaystyle |{mathcal {I}}|=q^{k}} Number of code words: |C|= |I|= qk{displaystyle |{mathcal {C}}|=|{mathcal {I}}|=q^{k}} Minimum distance: d {displaystyle d} Now stroke the last in the code words ( d – first {displaystyle d-1} ) the n {displaystyle n} Position, the other code words still have at least the Hamming distance 1. at d {displaystyle d} Deletions would no longer be guaranteed. So all code words are still different, so |C\u2032|= |C|= qk{displaystyle |{mathcal {C}}’|=|{mathcal {C}}|=q^{k}} That is why the number of length must also n – ( d – first ) {DisplayStyle N- (D-1)} Commerible words q n\u2212d+1\u2265 q k{displaystyle q^{n-d+1}geq q^{k}} be.If you change this equation, this results in the singleton barrier n – d + first \u2265 k \u21d4 d \u2264 n – k + first {displaystyle n-d+1geq kLeftrightarrow dleq n-k+1} For non-linear codes applies accordingly M \u2264 qn\u2212d+1{displaystyle Mleq q^{n-d+1}} , whereby M = | C| {displaystyle M=|{mathcal {C}}|} . Codes that meet the singleton barrier with equality is also called MDS codes. In the case of the Hamming barrier t = \u230a ( d – first ) \/ 2 \u230b {displaystyle t=lfloor (d-1)\/2rfloor } The number of the maximum correctional errors of a code with the Hamming distance d {displaystyle d} . The Hamming barrier says that qn\u2265 qk\u2211i=0t(q\u22121)i(ni){displaystyle q^{n}geq q^{k}{sum _{i=0}^{t}(q-1)^{i}{binom {n}{i}}}} , or n \u2265 k + logq\u2061 \u2211i=0t(q\u22121)i(ni){displaystyle ngeq k+log _{q}{sum _{i=0}^{t}(q-1)^{i}{binom {n}{i}}}} It must be fulfilled for a code that means n {displaystyle n} Symbols of an alphabet A {displaystyle Sigma } size q {displaystyle q} A message with the length k {displaystyle k} transported. For example n = 512 {displaystyle n=512} and t = 11 {displaystyle t=11} (requires a Hamming distance of d = 23 {displaystyle d=23} ) you get depending on the size q {displaystyle q} alphabets A {displaystyle Sigma } : q = 2 : k \u2264 438,374 6 {displaystyle q=2:kleq 438{,}3746} q = 4 : k \u2264 466,480 7 {displaystyle q=4:kleq 466{,}4807} q = 16 : k \u2264 482,857 2 {displaystyle q=16:kleq 482{,}8572} q = 28: k \u2264 491,808 6 {displaystyle q=2^{8}:kleq 491{,}8086} q = 216: k \u2264 496,400 4 {displaystyle q=2^{16}:kleq 496{,}4004} q = 232: k \u2264 498,700 2 {displaystyle q=2^{32}:kleq 498{,}7002} q = 264: k \u2264 499,850 first {displaystyle q=2^{64}:kleq 499{,}8501} q = 2128: k \u2264 500,425 0 {displaystyle q=2^{128}:kleq 500{,}4250} q = 2256: k \u2264 500,712 5 {displaystyle q=2^{256}:kleq 500{,}7125} q \u2192 \u221e : k \u2264 501,000 0 {displaystyle qto infty :kleq 501{,}0000} The Hamming barrier makes comparatively precisely precise statements depending on n {displaystyle n} , t {displaystyle t} and q {displaystyle q} . For very large q {displaystyle q} it strives for a limit. In the case of the singleton barrier is t = d – first {displaystyle t=d-1} The number of the maximum correctional errors of a code with the minimum distance d {displaystyle d} . For example n = 512 {displaystyle n=512} and t = 11 {displaystyle t=11} (requires a minimum distance of d = twelfth {displaystyle d=12} ) you get: k \u2264 501 {displaystyle kleq 501} irrespective of q {displaystyle q} . The singleton barrier is an inaccurate assessment than the hamming barrier, which does not take into account the size of the alphabet.There are also differences in the relationship between t {displaystyle t} and d {displaystyle d} . J.H. Van Lint: Introduction to Coding Theory (Graduate Texts in Mathematics) . 2nd Edition. Springer, Berlin, ISBN 978-3-540-54894-2.  Martin Bossert: Sewer coding . 3rd revised edition, Oldenbourg Verlag, Munich 2013, ISBN 3-486-72128-3. Otto Mildenberger (ed.): Information technology compact. Theoretical basics. Friedrich Vieweg & Sohn Verlag, Wiesbaden 1999, ISBN 3-528-03871-3. Werner Heise, Pasquale Quattrocchi: Information and coding theory . 2nd edition, Springer Verlag, Berlin \/ Heidelberg 1989, ISBN 978-3-540-50537-2.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2en\/wiki14\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2en\/wiki14\/singleton-barrier-wikipedia\/#breadcrumbitem","name":"Singleton barrier-Wikipedia"}}]}]