Binary String Generator With Minimum Distance

How do I generate 20 strings of binary numbers each of which are a minimum distance of 3 from all of the other strings?

Answer 1

[Akira Agata]

How about using BCH code ?

Theoretically, BCH(n,k) encoded binary sequences has minimun distance of bchnumerr(n,k)*2+1.

So if you generate BCH(15,11) encoded binary sequences, each pair of which has a minimum distance of 3.

% BCH(n,k) code
n = 15;
k = 11;

% Generate random binary sequence
seq = randi([0 1],20,k);

% Just in case, check if there is duplication
if size(unique(seq,'rows'),1) < 20
  warndlg('It has duplicated row(s) !','Warning')
end

% Encode by BCH(n,k)
msgTx = gf(seq);
enc = bchenc(msgTx,n,k);

% -> Then, enc becomes 20 binary sequences each of which are a min. distance of 3 

% Just in case, calculate hamming distance between each row
pt = nchoosek(1:size(enc,1),2);
d = zeros(size(pt,1),1);
for kk = 1:size(pt,1)
  d(kk) = nnz(enc(pt(kk,1),:) ~= enc(pt(kk,2),:));
end
disp(['Min. distance = ',num2str(min(d))])

The following is an example.

>> enc

enc = GF(2) array.

Array elements =

1 1 1 1 0 1 1 1 1 0 0 1 1 0 1

1 0 1 0 1 1 1 1 1 1 0 1 1 1 1

1 1 1 1 1 1 0 0 1 0 0 0 1 0 0

0 0 0 1 1 0 1 1 1 0 0 1 0 1 1

0 1 0 1 0 0 0 1 1 1 0 0 0 1 0

1 1 1 0 0 1 1 1 1 1 1 0 1 1 0

1 1 1 1 1 1 0 0 0 0 1 1 0 1 1

0 0 1 1 0 0 0 0 0 1 1 0 1 0 0

0 0 1 0 0 1 0 0 0 1 0 0 0 1 1

0 0 0 1 1 0 1 0 0 1 1 1 0 0 1

0 0 1 0 1 1 0 1 0 1 1 1 1 0 0

1 0 0 1 1 1 0 1 1 1 1 1 0 0 0

0 1 0 0 1 0 1 0 1 1 0 0 1 0 1

1 1 0 0 0 0 0 1 0 0 0 1 1 1 1

0 0 1 0 0 0 1 0 0 1 1 1 1 1 1

1 0 0 0 1 0 0 1 1 1 1 1 1 0 0

0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

0 0 1 1 1 1 0 0 1 1 0 0 1 1 0

0 0 1 1 1 0 1 1 1 0 1 0 1 1 1

1 0 1 1 1 1 1 0 1 1 0 1 0 1 0

>>

Min. distance = 3

[Anthony Mendez]

How were you able to come up with 15 as the code length, was this just arbitrary? Is there a way to know the minimum code length at which I could still generate 20 strings with the 3 distance minimum?

[Akira Agata]

OK, let me explain.

In BCH code, each code word has minimun d different bits ( = minimum distance of d). The value d depends on what kind of BCH was assumed.

In your case, d should be 3. And many BCH code can generate d = 3 code word, such as BCH(7,4), BCH(15,11), BCH(31,26)...etc.

If you chose BCH(7,4), the total number of code word is limited to 2^4 = 16, so this is insufficient (since you need 20 sequences).

That's why I choose BCH(15,11), which can generate 2^11 code word as maximum, as a possible solution.

For more details, please refer to some textbook on Forward Error Correction (FEC), or Error Correctin Code (ECC) technique.

Answer 2

[Lawrence Paul]

How can i implement matlab in computing the d_min for hamming code? Here is my code;

clear all;

close all;

clc;

m = 4;

n = 2^m-1; % length of the code

k = 5; % dimension of the code

[genpoly,t] = bchgenpoly(n,k) % compute generating polynomial and ecc

disp(genpoly); % coefficients of generator polynomial in descending order

disp(t); % error correcting capability

T = bchnumerr(n); %computes correctable errors of the BCH code under given parameter conditions

disp(T);

% possible values of k when n = 31 are 26,21,16,11,6 and correctable errors

% are 1,2,3,5,7 respectively

msg = gf([1 0 1 0 1 ; 0 1 0 1 0 ])

code = bchenc(msg,n,k); %encoding the bch code

display(code);