User kelvin lee - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T15:39:07Z http://mathoverflow.net/feeds/user/11105 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102159/good-codes-in-practice-for-correcting-combination-of-errors-and-erasures Good codes in practice for correcting combination of errors and erasures Kelvin Lee 2012-07-13T18:29:28Z 2013-05-14T02:21:55Z <p>In practice, both errors and erasures might be introduced in the channel. Could you point me to some good codes for correcting such combinations. Also what are their correction capabilities?</p> http://mathoverflow.net/questions/103664/inversion-vector-for-multiset-permutation inversion vector for multiset permutation Kelvin Lee 2012-08-01T07:09:21Z 2012-08-02T02:21:18Z <p>The definition of inversion vector for permutation is very well defined. Each permutation can be mapped to a unique inversion vector. So is there a well defined inversion vector for each multiset permutation, which maintains such one-to-one correspondence? I'm particularly interested in the multiset permutations where the multiplicity of each element is equal.</p> <p>Question added:</p> <p>For permutation, an inversion vector corresponds to a factoradic number, i.e., $i_k∈[0,i−1]$. The decimal number converted from the factoradic number could be used for ranking a permutation. Seems the inversion vector of a multiset permutation looses such good properties as the range of $i_k$ no longer only depends on i ? Or is there a numeral system similar to factoradic numeral system which corresponds to the inversion vector of a multiset permutation?</p> http://mathoverflow.net/questions/68486/doing-column-permutation-under-row-overlap-constraint Doing column permutation under row overlap constraint Kelvin Lee 2011-06-22T07:14:28Z 2012-07-15T16:54:21Z <p>In coding theory, there are parity-check codes whose parity-check matrices H are generated via column permutations. For instance, the LDPC codes constructed in Gallager's 1962 IRE Trans paper uses the following H matrix:</p> <p>[ X1 ]</p> <p>[ X2 ]</p> <p>[ .... ]</p> <p>[ Xn ]</p> <p>where submatrices X2 .. Xn are just random column permutations of X1. However, to make the codes efficient in decoding, there is one restriction which requires that any two row vectors in H mustn't have 2 or more overlapping elements. By overlapping, I mean for two different row vectors of H, say Va and Vb, there exists an index i s.t. Va[i] = Vb[i];</p> <p>I tried to write a program to do that, but so far my effort is not good. I'm wondering is there any known algorithmic way to adjust the permutated submatrices X1..Xn so that the overlapping constraint is satisfied? </p> <p>Thanks for your help!</p> http://mathoverflow.net/questions/98913/will-error-locating-codes-have-higher-rates-than-eccs Will "error locating codes" have higher rates than ECCs? Kelvin Lee 2012-06-05T22:10:48Z 2012-06-06T16:46:21Z <p>I'm wondering to detect all the errors (i.e. their positions) in a codeword $(c_0, c_1, \cdots, c_{n-1})\in Q$ where $Q$ is an alphabet set with size $q$, i.e., to know whether $c_i$ is faulty or not, without asking for the exact initial value. Is it possible to achieve higher code rate than the ECC which corrects errors?</p> <p>If so, could you show me or point me to some examples? For those famous ECCs such as BCH, Reed-Solomon Codes, LDPC codes, do they have the corresponding error locating versions which can have the higher rates?</p> http://mathoverflow.net/questions/96493/computing-channel-capacities-for-non-symmetric-channels Computing channel capacities for non-symmetric channels Kelvin Lee 2012-05-09T18:47:27Z 2012-05-10T17:03:43Z <p>I'm studying information theory right now and I'm reading about channel capacities. </p> <p>I know that there are known expressions for computing the capacities for some well known simple channels such as BSC, the Z channel. </p> <p>Could you show me or point me to the source showing how to derive the channel capacity for a binary asymmetric channel? Say that $X$ is input $Y$ is output. $\Pr(x = 0 | y = 1) = p_1$, $\Pr(x = 1 | y = 0) = p_2$.</p> <p>Further, I'm wondering is there any known result for computing the capacity of an arbitrary non-symmetric channel? By arbitrary non-symmetric channel, I mean, X and Y are from the alphabet set {${0, 1, \cdots, q-1}$}, and $\Pr(x = i \mid y = j) = p_{i, j}$ for $i, j \in$ {$0, 1, ..., q-1$}.</p> http://mathoverflow.net/questions/91403/do-these-random-variables-follow-gaussian-distribution Do these random variables follow Gaussian distribution? Kelvin Lee 2012-03-16T18:31:16Z 2012-03-17T02:29:14Z <p>Say that a random variable $X$ follows the Gaussian distribution $\mathcal{N}(\mu, \sigma)$. Then will the ceiling $\lceil X\rceil$, the floor $\lfloor X\rfloor$, and the rounding $\lfloor X\rceil$ follow some discrete Gaussian distributions? Could you prove or disprove it? And if they do follow, what are the means and the standard deviations?</p> http://mathoverflow.net/questions/103664/inversion-vector-for-multiset-permutation/103670#103670 Comment by Kelvin Lee Kelvin Lee 2012-08-01T15:02:59Z 2012-08-01T15:02:59Z For permutation, an inversion vector corresponds to a factoradic number, i.e., $i_k\in [0, i-1]$. The decimal number converted from the factoradic number could be used for ranking a permutation. Seems the inversion vector of a multiset permutation looses such good properties as the range of $i_k$ no longer only depends on $i$ ? Or is there a numeral system similar to factoradic numeral system which corresponds to the inversion vector of a multiset permutation? http://mathoverflow.net/questions/102159/good-codes-in-practice-for-correcting-combination-of-errors-and-erasures/102195#102195 Comment by Kelvin Lee Kelvin Lee 2012-07-14T02:41:17Z 2012-07-14T02:41:17Z Yes, I'm aware of the RS code, are there other codes which are also frequently used in practice for this purpose? http://mathoverflow.net/questions/98913/will-error-locating-codes-have-higher-rates-than-eccs/98933#98933 Comment by Kelvin Lee Kelvin Lee 2012-06-06T17:05:05Z 2012-06-06T17:05:05Z First, thanks for the nice answer! I'm sorry for misusing the term &quot;detection&quot; which causes the confusion. Yes, I actually meant &quot;locating&quot;. Right, I think the error locating codes and ecc which detect/correct the same number of errors will have the same rate. As for the error locating codes, the decoders can just go ahead and enumerate all the possible values at those faulty positions to and find a correct codeword as the enumeration space is finite. I don't have any application in my mind, I was just wondering whether using such a locating code will be more beneficial than using a ECC... http://mathoverflow.net/questions/98913/will-error-locating-codes-have-higher-rates-than-eccs Comment by Kelvin Lee Kelvin Lee 2012-06-06T16:49:46Z 2012-06-06T16:49:46Z Guys, sorry for misusing the term. Yes, the &quot;detection code&quot; I meant is actually &quot;error locating codes&quot;. I just edited the question and the title to use &quot;locating&quot; instead of &quot;detection&quot;. http://mathoverflow.net/questions/96493/computing-channel-capacities-for-non-symmetric-channels Comment by Kelvin Lee Kelvin Lee 2012-05-10T18:09:28Z 2012-05-10T18:09:28Z The answers below perfectly clear my confusions! http://mathoverflow.net/questions/96493/computing-channel-capacities-for-non-symmetric-channels/96528#96528 Comment by Kelvin Lee Kelvin Lee 2012-05-10T18:08:03Z 2012-05-10T18:08:03Z Your answer solves my last question so well! Also I appreciate the matlab code too, will definitely try to run it!