User kelvin lee - MathOverflow

Good codes in practice for correcting combination of errors and erasures

2012-07-13T18:29:28Z

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?

inversion vector for multiset permutation

2012-08-01T07:09:21Z

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.

Question added:

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?

Doing column permutation under row overlap constraint

2011-06-22T07:14:28Z

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:

[ X1 ]

[ X2 ]

[ .... ]

[ Xn ]

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];

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?

Thanks for your help!

Will "error locating codes" have higher rates than ECCs?

2012-06-05T22:10:48Z

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?

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?

Computing channel capacities for non-symmetric channels

2012-05-09T18:47:27Z

I'm studying information theory right now and I'm reading about channel capacities.

I know that there are known expressions for computing the capacities for some well known simple channels such as BSC, the Z channel.

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$.

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$}.

Do these random variables follow Gaussian distribution?

2012-03-16T18:31:16Z

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?

Comment by Kelvin Lee

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?

Comment by Kelvin Lee

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?

Comment by Kelvin Lee

2012-06-06T17:05:05Z

First, thanks for the nice answer! I'm sorry for misusing the term "detection" which causes the confusion. Yes, I actually meant "locating". 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...

Comment by Kelvin Lee

2012-06-06T16:49:46Z

Guys, sorry for misusing the term. Yes, the "detection code" I meant is actually "error locating codes". I just edited the question and the title to use "locating" instead of "detection".

Comment by Kelvin Lee

2012-05-10T18:09:28Z

The answers below perfectly clear my confusions!

Comment by Kelvin Lee

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!