ハミング限界

ハミング限界（ハミングげんかい、英: Hamming bound）は、符号（線型符号とは限らない）のパラメータの限界値を指す。球充填の限界を情報理論の観点で言い直したものと言える。ハミング限界に従った符号を「完全符号; perfect code」と呼ぶ。

定義

q進数の符号 $C$ が長さ $n$ で最小ハミング距離 $d$ であるとき、その可能な最大サイズ（符号語の総数）を $A_{q}(n,d)$ とする。なお、q進数の符号は、 $q$ 個の要素の体 $\mathbb {F} _{q}^{n}$ 上の線型符号である。

すると、次が成り立つ。

A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}

ここで、

t=\lfloor {\frac {d-1}{2}}\rfloor

証明

$d$ の定義から、符号語の転送において最大で $t=\lfloor {\tfrac {d-1}{2}}\rfloor$ の誤りが発生したとすると、最小距離復号によって正しく復号できる（すなわち、符号化された符号語を正しく復号できる）。つまり、この符号は $t$ 個の誤りを訂正可能である。

$c\in C$ であるようなある符号語について、 $c$ を中心とする半径 $t$ の球を考える。このような球の範囲内なら誤り訂正が正しく行われる。符号語を構成する $n$ 個の要素のうち $t$ 個まで誤りがあっても正しく復号できるため、それぞれの球には以下の符号語が含まれる（つまり、中心にある真の符号語の一部を変更した符号語群の数）。符号語の一桁は q進数であるから、とりうる値は $(q-1)$ 種類になる。

\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}

$C$ に存在する符号語の総数を $M$ とする。全ての符号語から球の和集合をとると、結果として得られる符号語の総数は $\mathbb {F} _{q}^{n}$ 以内となる。それぞれの球は重ならないので、それぞれの要素数の総和をとると、次が成り立つといえる。

M\times \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\leq \vert \mathbb {F} _{q}^{n}\vert =q^{n}

従って、次が導かれる。

A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}

Read other articles:

Bambang Waskito

Bambang Waskito Kasespim Lemdiklat PolriMasa jabatan21 Desember 2018 – 2 September 2019 PendahuluWahyu Indra PramugariPenggantiPrasta Wahyu HidayatKepala Kepolisian Daerah Sulawesi UtaraMasa jabatan12 Desember 2016 – 21 Desember 2018 PendahuluWilmar MarpaungPenggantiRemigius Sigid Tri HardjantoKepala Kepolisian Daerah Jawa BaratMasa jabatan27 Mei 2016 – 12 Desember 2016 PendahuluJodie RoosetoPenggantiAnton Charliyan Informasi pribadiLahir8 November 1961 (umur&...

Dazzler (Marvel Comics)

Marvel Comics fictional character Comics character DazzlerDazzler on the cover of Dazzler #20, art by John Romita Jr.Publication informationPublisherMarvel ComicsFirst appearanceThe Uncanny X-Men #130(February 1980)Created byTom DeFalcoJohn Romita Jr.In-story informationAlter egoAlison Ali BlaireSpeciesHuman mutantTeam affiliations Gladiators New Excalibur The 198 S.H.I.E.L.D. X-Men Wildways Rebellion A-Force Heralds of Galactus Notable aliasesThe Disco DazzlerAbilities Ability to convert sou...

Kuku (food)

Food KukuKuku sabzi (herb kuku) topped with barberries and walnutsTypeOmeletteCourseSide dish, main course, or midday coursePlace of originIranAssociated cuisineIranian cuisineMain ingredientsEggsVariationsHerb kuku, potato kuku, eggplant kukuSimilar dishesFrittata, Quiche, Eggah Media: Kuku Kuku or kookoo (Persian: کوکو) is an egg-based and often vegetarian Iranian dish made of whipped eggs folded in various ingredients. It is similar to the Italian frittata, the French quiche,...

Victor Riley

Victor Riley Nazionalità Stati Uniti Altezza 196 cm Peso 154 kg Football americano Ruolo Offensive tackle Termine carriera 2005 CarrieraGiovanili Auburn TigersSquadre di club 1998-2001 Kansas City Chiefs2002-2004 New Orleans Saints2005 Houston Texans Modifica dati su Wikidata · Manuale Victor Allan Riley (Swansea, 4 novembre 1974 – 8 aprile 2024[1]) è stato un giocatore di football americano statunitense che ha militato nel ruolo di offensi...

土库曼斯坦总统

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府（Oguzkhan Presidential Palace）機關所在地阿什哈巴德任命者直接选举任期7年，可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日土库曼斯坦土库曼斯坦政府与政治国家政府土库曼斯坦宪法国旗国徽国歌立法機關（英语：National Council of Turkmenistan） ...

Psalm 25

Biblical psalm This article is about Psalm 25 in Hebrew (Masoretic) numbering. For Psalm 25 in Greek Septuagint or Latin Vulgate numbering, see Psalm 26. Psalm 25Unto thee, O LORD, do I lift up my soul.Verses 1 to 7a of Psalm 25 (Psalmus 24) in the 12th-century St. Albans PsalterOther name Psalm 24 (Vulgate) Ad te Domine levavi animam meam LanguageHebrew (original) Psalm 25← Psalm 24Psalm 26 →BookBook of PsalmsHebrew Bible partKetuvimOrder in the Hebrew part1CategorySifrei EmetC...

Condé-sur-Aisne

Condé-sur-AisnecomuneCondé-sur-Aisne – VedutaLa chiesa dei Santi Pietro e Paolo a Condé-sur-Aisne LocalizzazioneStato Francia RegioneAlta Francia Dipartimento Aisne ArrondissementSoissons CantoneFère-en-Tardenois TerritorioCoordinate49°24′N 3°27′E / 49.4°N 3.45°E49.4; 3.45 (Condé-sur-Aisne)Coordinate: 49°24′N 3°27′E / 49.4°N 3.45°E49.4; 3.45 (Condé-sur-Aisne) Superficie3,74 km² Abitanti404[1] (2009) Densità10...

豪栄道豪太郎

豪栄道豪太郎場所入りする豪栄道基礎情報四股名澤井豪太郎→豪栄道豪太郎本名澤井豪太郎愛称ゴウタロウ、豪ちゃん、GAD[1][2]生年月日 (1986-04-06) 1986年4月6日（38歳）出身大阪府寝屋川市身長 183cm体重 160kgBMI 47.26所属部屋境川部屋得意技右四つ・出し投げ・切り返し・外掛け・首投げ・右下手投げ成績現在の番付引退最高位東大関生涯戦歴 696勝493敗...

Magnus Hirschfeld

Magnus HirschfeldHirschfeld pada 1929Lahir(1868-05-14)14 Mei 1868Kolberg, Provinsi Pomerania, Kerajaan Prussia, Konfederasi Jerman Utara (kini Kołobrzeg, Polandia)Meninggal14 Mei 1935(1935-05-14) (umur 67)Nice, Republik Ketiga PrancisTempat tinggalJerman, PrancisDikenal atasInstitut für Sexualwissenschaft, Komite Kemanusiaan Ilmiah Magnus Hirschfeld (14 Mei 1868 – 14 Mei 1935) adalah fisikiwan dan seksolog Yahudi Jerman yang terdidik terutama di Jerman; ia melakukan praktik di Berli...

List of Malayalam films of 1989

Malayalam cinema Before 1960 1960s 1960 1961 1962 1963 19641965 1966 1967 1968 1969 1970s 1970 1971 1972 1973 19741975 1976 1977 1978 1979 1980s 1980 1981 1982 1983 19841985 1986 1987 1988 1989 1990s 1990 1991 1992 1993 19941995 1996 1997 1998 1999 2000s 2000 2001 2002 2003 20042005 2006 2007 2008 2009 2010s 2010 2011 2012 2013 20142015 2016 2017 2018 2019 2020s 2020 2021 2022 2023 2024 vte The following is a list of Malayalam films released in the year 1989. Film Director Screenplay Cast Mr...

Left Unity (UK)

Political party in the United Kingdom Left Unity Principal SpeakersSharon McCourt Felicity Dowling Nick Jones[1]National SecretaryFelicity Dowling[1]Founded30 November 2013 (2013-11-30)Membership (July 2016) 1,230IdeologyEco-socialism[2]Anti-capitalismEnvironmentalismFeminismPro-EuropeanismPolitical positionLeft-wingNational affiliationPeople's Alliance of The Left[3]European affiliationParty of the European Left[4]Colours ...

Kyōteijō-mae Station

This article is about the station in Tokyo. For the station in Hiroshima formerly named Kyōteijō-mae Station, see Miyajima Boat Race Jō Station. Railway station in Fuchū, Tokyo, Japan SW05Kyōteijō-mae Station競艇場前駅Kyōteijō-mae Station south entrance, 2012General informationLocation4-10-11 Koyanagi-cho, Fuchū-shi, Tokyo 183-0013JapanCoordinates35°39′22″N 139°29′58″E / 35.65611°N 139.49944°E / 35.65611; 139.49944Operated by Seibu RailwayLine...

Seth Berkley

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. Seth BerkleBerkley di World Economic Forum Annual Meeting of the New Champions pada 2012Lahir18 Oktober 1956 (umur 67)New York City, Amerika SerikatPendidikanUniversitas Brown (BA, MD)Dikenal atasPendiri dan mantan presiden dan CEO International A...

Dawn of the Planet of the Apes (soundtrack)

2014 film score by Michael GiacchinoDawn of the Planet of the Apes (Original Motion Picture Soundtrack)Film score by Michael GiacchinoReleasedJuly 7, 2014Recorded2014StudioNewman Scoring Stage,Twentieth Century Fox StudiosGenreFilm scoreLength77:21LabelSony ClassicalProducerMichael GiacchinoMichael Giacchino chronology Star Trek Into Darkness(2013) Dawn of the Planet of the Apes(2014) This Is Where I Leave You(2014) Planet of the Apes soundtrack chronology Rise of the Planet of the Ap...

George Nugent, 1st Marquess of Westmeath

Anglo-Irish peer The Most HonourableThe Marquess of Westmeathportrait as a child by Gilbert Stuart, c. 1789-90Lord Lieutenant of WestmeathIn office1831–1871Preceded byOffice establishedSucceeded byThe Lord Greville Personal detailsBorn17 July 1785Died5 May 1871 (aged 85)Spouse(s)Emily Cecil (m. 1812 div. 1827)Maria Jervis (m. 1858 div. 1862)Elizabeth Verner (m. 1864 d. 1882)ChildrenWilliam (1818-1819)Rosa (1814-1883)Eliza (1806-1877) (illegitimate)Cecilia (1849-1886) (illegitimate) George T...

UEFA Intertoto Cup

European association football tournament for clubs Football tournamentUEFA Intertoto CupOrganising bodyUEFA (from 2001)Founded1961; 63 years ago (1961)Abolished2008; 16 years ago (2008)RegionEuropeNumber of teams50Related competitionsUEFA Cup (merged with)Last champions Braga(1st title)Most successful club(s) Hamburger SV Schalke 04 VfB Stuttgart Villarreal(2 titles each) Hamburger SV won the UEFA Intertoto Cup two times, a record jointly held with Schalke ...

Back to You (Selena Gomez song)

2018 single by Selena Gomez Back to YouSingle by Selena Gomezfrom the album 13 Reasons Why: Season 2 (Music from the Original TV Series) ReleasedMay 10, 2018 (2018-05-10)Genre Dance-pop electropop Length3:30LabelInterscopeSongwriter(s) Parrish Warrington Diederik Van Elsas Amy Allen Micah Premnath Selena Gomez Producer(s) Trackside Ian Kirkpatrick Selena Gomez singles chronology Wolves (2017) Back to You (2018) Taki Taki (2018) Music videoBack to You on YouTube Back to You is a...

Cliff Compton

Cliff ComptonDonnées généralesNom de naissance Cliff ComptonNom de ring Cliff ComptonDice DominoDominoNationalité AméricainNaissance 2 novembre 1979 (44 ans)Comté de NassauTaille entre 6′ 1″ (1,85 m)[1] et 6′ 2″ (1,88 m)[2],[3]Poids entre 220 lb (100 kg)[1] et 240 lb (109 kg)[2],[3]Catcheur retraitéFédération Florida Championship WrestlingOhio Valley WrestlingRing Of HonorWorld Wrestling EntertainmentEntraîneur Monster FactoryOVW ...

東海道貨物線

この項目では、首都圏地区の東海道本線・南武線の貨物線・貨物支線の一部について説明しています。首都圏地区の東海道本線の貨物支線のうち、品川駅 - 新鶴見信号場 - 鶴見駅間については「品鶴線」をご覧ください。首都圏地区の東海道本線の貨物支線のうち、鶴見駅 - 東高島駅 - 桜木町駅間については「高島線」をご覧ください。大阪地区の東海道本線の貨物�...

モンゴル高原

モンゴル高原所在地モンゴル中国ロシア種類高原プロジェクト山テンプレートを表示モンゴル高原各種表記繁体字：蒙古高原簡体字：蒙古高原発音：モンゴルコウゲン広東語発音：蒙古高原ウイグル語： موڭغۇلىيە ئېگىزلىكىチベット語： སོག་པོའི་མཐོ་སྒང་།モンゴル語： Монголын өндөрлөг日本語読み：モンゴル高原韓国語： �...

PROFILPELAJAR.COM