翻訳と辞書 Words near each other ・ Gušće ・ Guščerovec ・ Guźlin ・ Guźnia ・ Guždelji ・ Gușoeni ・ Gușoeni River ・ Gușterița ・ Guțan River ・ Guṇa ・ Guṇabhadra ・ GV ・ GV (nerve agent) ・ GV Florida Transport ・ GV Yishun ・ GV-linear-code ・ GVA ・ GVA (business) ・ GVA Consultants ・ Gvantsa Kakhaberidze ・ Gvar'am ・ Gvardeysk ・ Gvardeyskoye, Kaliningrad Oblast ・ Gvardeysky ・ Gvardeysky District ・ Gvardeysky, Kazakhstan ・ Gvardeysky, Russia ・ Gvarv ・ Gvat ・ GVAX Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク GV-linear-code ： ウィキペディア英語版 GV-linear-code In coding theory, the bound of parameters such as rate ''R'', relative distance, block length, etc. is usually concerned. Here Gilbert–Varshamov bound theorem claims the lower bound of the rate of the general code. Gilbert–Varshamov bound is the best in term of relative distance for codes over alphabets of size less than 49. ==Gilbert–Varshamov bound theorem== Theorem: Let $q\; \backslash ge\; 2$. For every , and , there exists a code with rate $R\; \backslash ge\; 1\; -\; H\_q\; (\backslash delta\; )\; -\; \backslash varepsilon$, and relative distance $\backslash delta$. Here $H\_q$ is the ''q''-ary entropy function defined as follows: : $H\_q(x)\; =\; x\backslash log\_q(q-1)-x\backslash log\_qx-(1-x)\backslash log\_q(1-x).$ The above result was proved by Edgar Gilbert for general code using the greedy method as here. For linear code, Rom Varshamov proved using the probabilistic method for the random linear code. This proof will be shown in the following part. ''High-level proof:'' To show the existence of the linear code that satisfies those constraints, the probabilistic method is used to construct the random linear code. Specifically the linear code is chosen randomly by choosing the random generator matrix $G$ in which the element is chosen uniformly over the field $\backslash mathbb\_q^n$. Also the Hamming distance of the linear code is equal to the minimum weight of the codeword. So to prove that the linear code generated by $G$ has Hamming distance $d$, we will show that for any $m\; \backslash in\; \backslash mathbb\_q^k\; \backslash backslash\; \backslash left\backslash ,\; wt(mG)\; \backslash ge\; d$ . To prove that, we prove the opposite one; that is, the probability that the linear code generated by $G$ has the Hamming distance less than $d$ is exponentially small in $n$. Then by probabilistic method, there exists the linear code satisfying the theorem. ''Formal proof:'' By using the probabilistic method, to show that there exists a linear code that has a Hamming distance greater than $d$, we will show that the probability that the random linear code having the distance less than $d$ is exponentially small in $n$. We know that the linear code is defined using the generator matrix. So we use the "random generator matrix" $G$ as a mean to describe the randomness of the linear code. So a random generator matrix $G$ of size $kn$ contains $kn$ elements which are chosen independently and uniformly over the field $\backslash mathbb\_q$. Recall that in a linear code, the distance = the minimum weight of the non-zero codeword. This fact is one of the properties of linear code. Denote $wt(y)$ be the weight of the codeword $y$. So : $$ \begin P & = _ () \end Also if codeword $y$ belongs to a linear code generated by $G$, then $y\; =\; mG$ for some vector $m\; \backslash in\; \backslash mathbb\_q^k$. Therefore : $P\; \backslash le\; \backslash sum\backslash limits\_\; \}\; =\; q^k\; q^$ By choosing $k\; =\; (1-H\_q(\backslash delta)-\backslash varepsilon)n$, the above inequality becomes : $P\; \backslash le\; q^$ Finally $q^\; \backslash ll\; 1$, which is exponentially small in n, that is what we want before. Then by the probabilistic method, there exists a linear code $C$ with relative distance $\backslash delta$ and rate $R$ at least $(1-H\_q(\backslash delta)-\backslash varepsilon)$, which completes the proof. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「GV-linear-code」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.