MATLAB Answers

Binary String Generator With Minimum Distance

15 views (last 30 days)
Anthony Mendez
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?

  0 Comments

Sign in to comment.

Accepted Answer

Akira Agata
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

  2 Comments

Anthony Mendez
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
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.

Sign in to comment.

More Answers (0)

Sign in to answer this question.