Как заполнить матрицу единицами из их распределений по строкам и столбцам
Мне нужно заполнить матрицу с "1" и "0". Предоставленные данные представляют собой размеры матрицы и распределения строк и столбцов единицы (через два разных вектора, поскольку они могут быть разными для каждого случая). Таким образом, у нас есть два вектора, v и h, элементы которых определены как:
v_i = i-th element of vector v.
Указывает долю столбцов с весом i (доля столбцов от общего количества, которые содержат i '1).
fh_i = i-th element of vector h.
Указывает долю строк с весом i (доля строк по итогу, которые содержат i '1).
Принятая во внимание процедура называется алгоритмом МакКея Нила. Состоит из заполнения матрицы в столбце слева направо. Вес каждого столбца выбирается для получения правильного распределения "1". Расположение этих "1" в каждом файле выбирается случайным образом из тех, которые еще не заполнены.
Пожалуйста, найдите прикрепленный мой код прямо ниже. Вы также можете найти на этой веб-странице PDF-документ, с которым я сейчас консультируюсь, чтобы выполнить эту часть моего проекта. Все, что я упомянул заранее, можно найти на страницах 10 и 11. Алгоритм MacKay реализован в псевдокоде на странице 14.
function H = MacKayNeal(N,r,v,h)
H = zeros(N*(1-r),N);
a = [];
for i=1:length(v)
for j=1:(v(i)*N)
a = [a,i];
end
end
b = [];
for i=1:length(h)
for j=1:(h(i)*(N*(1-r)))
b = [b,i];
end
end
for i=1:N
c = datasample(b,length(a(i)),'Replace',false);
for j=1:a(i)
H(c(j),i)=1;
end
a = a - c;
end
% while 1 % cycles removed
% for i=1:(N-1)
% for j=(i+1):N
% if 1 %
% end
% end
% end
% end
end
Обратите внимание, что значения "a" и "b" соответственно относятся к переменным "alpha" и "beta", используемым в псевдокоде прикрепленного текста. Их значения указывают количество "1" на столбец и файл в каждом случае.
В моем случае все шло хорошо, пока я не выполнил вычитание "a = a - c" в строке 20. Я провел целый день, ломая себе мозги, и в итоге вышли два вопроса:
Почему это вычитание "a = a - c", а не "b = b - [одно целое в каждой соответствующей позиции из c]? Для меня было бы гораздо больше смысла в отношении того, что появляется в объяснении теории перед псевдокодом в PDF-документе, прилагаемом по ссылке.
Что произойдет, если вы выберете подмножество b, которое содержит по крайней мере два равных значения для выполнения следующего назначения "1" в H-матрице? Мне кажется, что это вполне осуществимая ситуация, в которой a_i '1 не будут добавлены, но меньше этого.
Если кто-то также может помочь мне с решением последней части задачи, в которой в псевдокоде упоминается стирание циклов длиной 4 '(это просто означает, что в двух отдельных столбцах не может быть двух пар' 1, занимающих одинаковые позиции). Я также был бы очень благодарен.
В моем случае я работаю со следующими данными:
N = 100
k = 0.5
v = [0 0.17 0.03 0.2 0 0 0.17 0.3 0.03 0.1]
h = [0 0.1 0 0 0 0.7 0.2]
Для обоих векторов v и h их элементы могут принимать любое значение от 0 до 1, если их сумма равна 1 в обоих случаях, а первый элемент равен 0 также в обоих случаях. Кроме того, k tan принимает любое значение от 0 до 1.
Заранее большое спасибо за внимание!
Редактировать 01/01/2017
Следуя приведенным выше образцам значений, я столкнулся со следующей проблемой. Там вы также можете посмотреть обновленную версию моего кода (все предыдущие предложения остались прежними).
В этом случае при заданном распределении "h" может быть только три разных значения (2, 6 и 7) для каждого элемента из β-вектора. Для тех случаев, когда αi больше трех (в нашем примере это может быть до десяти), вектор c будет иметь как минимум два одинаковых значения, несмотря на попытку избежать этого в предложении "образец данных".
Я полагаю, это то, что вы имели в виду ранее, когда упомянули, что этот алгоритм не всегда завершается, но в этом случае он никогда этого не сделает!
Редактировать 01/03/2017
Теперь у меня есть еще одна проблема, связанная со строительством векторов а / б. Моя проблема в том, что когда N велико, например, N = 100, и, следовательно, размерность нашей матрицы для r = 0,5 (50x100) будет иметь вектор, представляющий распределение весов столбцов длины 1x100. Позвольте мне привести один краткий пример. Мы можем, например, иметь распределение столбцов, которое состоит из v_2 = 0.8258 (напомним, что согласно спецификациям v_1 = 0) и остальные значения до v_100 гораздо меньше, например, вокруг v_i = 0.0018 или так в нашем случае.
Наш код не сработает в этом случае, так как эти значения будут намного меньше 1, если их умножить на N = 100 (подробнее см. Ниже мое предлагаемое решение). Это значит, что не будет никаких столбцов с весом 1 или более, даже если сумма всех их достигает единицы в соответствии с теорией. Ко времени выполнения алгоритма индекс i не будет работать до N = 100, но до 82 для этого случая (и та же проблема происходит с векторами h/b). Для лучшего понимания моей проблемы я рекомендую запустить мой код ниже со следующими параметрами:
N = 100;
r = 0.5;
v = [0 0.8258 0.0048 0.0033 0.0027 0.0024 0.0023 0.0022 0.0021 0.0020 0.0019 0.0019 0.0019 0.0019 0.0019 0.0019 0.0018 0.0018 0.0018 0.0018 0.0018 0.0018 0.0018 0.0018 0.0018 0.0018 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0016 0.0016 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0017 0.0016 0.0016 0.0016 0.0016 0.0017 0.0017 0.0017 0.0016 0.0017 0.0017 0.0016 0.0016 0.0016 0.0016 0.0017 0.0017 0.0017 0.0016 0.0016 0.0016 0.0017 0.0017 0.0017 0.0016 0.0017 0.0016 0.0016 0.0016 0.0016 0.0016 0.0017 0.0016 0.0017 0.0016 0.0016 0.0016 0.0016 0.0016 0.0016 0.0016 0.0017];
h = [0 0.0179 0.0102 0.0277 0.0392 0.0272 0.0027 0.0055 0.0148 0.0151 0.0137 0.0259 0.0103 0.0336 0.0386 0.0049 0.0065 0.0051 0.0081 0.0441 0.0298 0.0147 0.0243 0.0207 0.0198 0.0006 0.0287 0.0425 0.0088 0.0094 0.0368 0.0090 0.0181 0.0306 0.0158 0.0325 0.0108 0.0268 0.0163 0.0448 0.0395 0.0262 0.0097 0.0114 0.0283 0.0437 0.0103 0.0058 0.0249 0.0083];
Большое спасибо заранее и наилучшими пожеланиями.
2 ответа
Я верю, что вы правы, и обе ваши точки зрения являются ошибками в конспектах лекций.
Я думаю, что это имеет больше смысла, если мы заменим:
c = random subset of β, of size αi
for j = 1 : αi do
H(cj , i) = 1
end for
α = α − c
с
c = random distinct subset of β, of size αi (not allowed to return elements of the same value)
for j = 1 : αi do
H(cj , i) = 1
end for
β = β − c
Раздел 3.2 "НОВОГО СТРОИТЕЛЬСТВА КОДОВ LDPC КРАТКОЙ ДЛИНЫ ДЛЯ ПРОСТОГО ДЕКОДИРОВАНИЯ" Фатмы А. Ньюэджи, Ясмин А. Фахми и Магди М. С. Эль-Судани содержит эту версию алгоритма (при этом вы берете на себя роль β)
Один из простых способов настройки кода Matlab - просто повторить шаг выборки данных, пока все элементы не будут различны.
Обратите внимание, что этот алгоритм не всегда завершается, поэтому я рекомендую отслеживать количество повторных попыток и начинать заново (с начала или за несколько шагов до этого), если это число становится слишком большим.
Обратите внимание, что существует два основных варианта этого алгоритма:
Алгоритм 1
(Я считаю, что это оригинальный алгоритм Маккея Нила)
Вектор с длиной, равной количеству строк, хранит желаемый вес каждой строки.
Когда выбирается случайная выборка строк, 1 вычитается из соответствующих записей в векторе, чтобы отметить, что эти строки теперь имеют меньший желаемый вес.
Алгоритм 2
(Я считаю, что это общее улучшение.)
Чтобы повысить вероятность получения правильного распределения рядов, лучше сместить образец в сторону рядов, которым требуется больший вес.
Это делается путем подготовки вектора длины, равного общему количеству единиц во всей матрице. Элементы вектора соответствуют номерам строк.
Случайная выборка этого вектора предоставляет набор номеров строк. Эти записи удаляются из вектора.
Так, например, если мы хотим в конечном итоге иметь четыре 1 в строке 2, то число 2 (соответствующее строке 2) будет четыре раза появляться в векторе. Это означает, что строка 2 будет выбрана четыре раза и, следовательно, будет иметь четыре единицы.
Я считаю, что псевдокод относится к этому второму алгоритму.
Это означает, что если β=[1,1,2,2,3,3] и мы выбираем вектор c из [2,3], то операция β-c должна производить вывод [1,1,2,3].
Ну, похоже, я наконец-то это сделал!
У меня было два недоразумения с приложенным псевдокодом, как я и предполагал. Вот одно решение, которое работает для меня:
function H = MacKayNeal(N,r,v,h)
H = zeros(N*(1-r),N);
a = [];
for i=1:length(v)
for j=1:(v(i)*N)
a = [a,i];
end
end
b = [];
for i=1:length(h)
for j=1:(h(i)*(N*(1-r)))
b = [b,i];
end
end
b_i = 1:length(b);
for i=1:N
for j=1:1:length(b)
if b(j) == 0
b_i = setdiff(b_i,b);
end
end
c = datasample(b_i,a(i),'Replace',false);
c_i = zeros(length(b));
for j=1:a(i)
H(c(j),i)=1;
c_i(1,c(j))=1;
end
b = b - c_i;
end
% Removal of length-4 cycles
for i=1:N*(1-r)-1
for j=i+1:N*(1-r)
w = and(H(i,:),H(j,:));
c1 = find(w);
lc = length(c1);
if lc > 1
% If found, flip one 1 to 0 in the row with less number of 1s
if length(find(H(i,:))) < length(find(H(j,:)))
% Repeat the process until only one column left
for cc = 1:(lc-1)
H(j,c1(cc)) = 0;
end
else
for cc = 1:(lc-1)
H(i,c1(cc)) = 0;
end
end
end
end
end
конец
Как каждый из вас может видеть, я наконец заменил вычитание " a = a - c " на " b = b - c_i ". А что такое c_i? Это просто вектор, содержащий в индексах элементы, которые я извлек из b. Таким образом, я мог бы наконец реализовать H-матрицу без каких-либо других проблем.
Спасибо всем за поддержку и наилучшие пожелания!
Редактировать 13/03/2017
Как уже упоминалось в первом вопросе, этот код не будет работать для любого распределения степени.
Я хотел бы, чтобы это работало для тех случаев, когда получается довольно нерегулярное распределение степеней. Пусть у нас есть, например, следующие параметры:
v = [0 0.6895 0.0011 0.0003 0.0001 0.0525 0.0009 0.0111 0.0805 0.0077 0.0097 0.0019 0.0011 0.0009 0.0008 0.0019 0.0014 0.0006 0.0012 0.0031 0.0007 0.0022 0.0019 0.0006 0.0014 0.0096 0.0023 0.0018 0.0015 0.0074 0.0022 0.0011 0.0005 0.0010 0.0003 0.0017 0.0006 0.0007 0.0009 0.0033 0.0365 0.0030 0.0006 0.0449 0.0018 0.0000 0.0021 0.0012 0.0015 0.0005];
h = [0 0.0178 0.0167 0.0004 0.0034 0.0020 0.0121 0.0106 0.0063 0.0064 0.0025 0.0061 0.0005 0.0158 0.0150 0.0202 0.0036 0.0149 0.0020 0.0034 0.0140 0.0035 0.0054 0.0163 0.0054 0.0017 0.0202 0.0195 0.0183 0.0007 0.0022 0.0193 0.0196 0.0178 0.0171 0.0021 0.0096 0.0033 0.0090 0.0199 0.0061 0.0076 0.0101 0.0177 0.0188 0.0110 0.0136 0.0092 0.0025 0.0199 0.0148 0.0137 0.0143 0.0036 0.0010 0.0011 0.0077 0.0040 0.0054 0.0164 0.0136 0.0127 0.0176 0.0147 0.0170 0.0040 0.0173 0.0008 0.0200 0.0017 0.0030 0.0016 0.0081 0.0030 0.0118 0.0167 0.0199 0.0157 0.0186 0.0056 0.0166 0.0110 0.0140 0.0095 0.0108 0.0008 0.0107 0.0038 0.0112 0.0078 0.0063 0.0145 0.0192 0.0044 0.0158 0.0062 0.0096 0.0100 0.0039 0.0072];
N = 100;
r = 0.5;
Можете ли вы помочь мне исправить это?
v и h являются результатом проблемы оптимизации (которую, я надеюсь, я решил правильно). Вы можете найти больше информации об этом в начале моего поста.
Большое спасибо заранее и наилучшими пожеланиями.