# Binary String Generator With Minimum Distance

15 views (last 30 days)
Anthony Mendez on 10 Jul 2019
Edited: Akira Agata on 11 Jul 2019
How do I generate 20 strings of binary numbers each of which are a minimum distance of 3 from all of the other strings?

Akira Agata on 11 Jul 2019
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 on 11 Jul 2019
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 on 11 Jul 2019
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.