secret
Created

Estimate the minimum string length to produce a set of a given size with a minimum pairwise Hamming distance

  • Download Gist
gistfile1.r
R
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
# Use the Gilbert-Varshamov bound to estimate the minimum string length (n) that
# is required to construct a set of size x of sequences using an alphabet of size q
# with minimum Hamming distance d between any two strings in the set.
# See http://mathoverflow.net/questions/104309/how-to-find-the-minimum-string-length-to-produce-a-set-of-a-given-size-with-a-min
estimate.min.string.length <- function(x, q, d) {
if (q < 2) stop("q must be >= 2")
if (d < 1) stop("d must be >= 1")
A <- 0
# I am fairly certain by cannot prove that this is the minimum bound on n
n <- max(1, floor(log(x, q)))
while (TRUE) {
A <- gilbert.varshamov(n, q, d)
if (A < x) {
n <- n + 1
}
else {
return(n)
}
}
}
 
gilbert.varshamov <- function(n, q, d) {
denom <- 0
for (j in 0:(d-1)) {
denom <- denom + (choose(n, j) * ((q - 1)^j))
}
(q^n) / denom
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.