Rank deficient LDPC code
$begingroup$
I am new to working on LDPC codes and have gotten stuck on this issue for some time. I am struggling on how to deal with parity check matrices that are not of full rank. I generate the parity check matrix using Gallager's construction (see example 1.14 http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf) and then attempt to get the result into systematic form, so that the matrix describes the information part and the parity part. When I do this however I am left with one or more all zero rows and to double check I checked the rank and it is indeed not full rank matrix.
The question I have is, what do I do when the parity check matrix starts out as not full rank? How do I get the systematic form and then the generator matrix? And what is the meaning of the parity check matrix not being full rank?
galois-theory coding-theory
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
$endgroup$
add a comment |
$begingroup$
I am new to working on LDPC codes and have gotten stuck on this issue for some time. I am struggling on how to deal with parity check matrices that are not of full rank. I generate the parity check matrix using Gallager's construction (see example 1.14 http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf) and then attempt to get the result into systematic form, so that the matrix describes the information part and the parity part. When I do this however I am left with one or more all zero rows and to double check I checked the rank and it is indeed not full rank matrix.
The question I have is, what do I do when the parity check matrix starts out as not full rank? How do I get the systematic form and then the generator matrix? And what is the meaning of the parity check matrix not being full rank?
galois-theory coding-theory
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
$endgroup$
2
$begingroup$
If you construct this matrix in a random way, we can get a parity check matrix which is not full rank effectively. The redundant columns are useless for a code construction point of view. You can suppress them to get a systematic construction. But pay attention that this encoding method is not suitable for large sizes, as the obtained generating matrix is not sparse. For a decoding point a view, you can keep these redundant columns: the iterative decoding process is not optimal and you may loose in performance by suppressing these columns
$endgroup$
– Damien
Dec 11 '18 at 14:23
$begingroup$
@Damien That makes sense, thank you. The redundant columns are in some way representing a coded bit that it doesn't matter what its value is? Is this a correct way of thinking of the redundant columns?
$endgroup$
– BryanEhlers
Dec 11 '18 at 20:25
$begingroup$
I'm fairly sure that you are supposed to do the decoding with the original sparse check matrix. Linear dependencies among the check equations do create cycles in the Tanner graph, but unless they are relatively short, they won't disturb the decoding much. To have efficient encoding you do need to know the set of information positions at least. A high weight generator matrix may be bad for filling in the check positions. I'm afraid I'm not up to speed with all the related aspects for I have only ever seriously looked at LDPC codes with a little bit of extra structure.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 6:08
add a comment |
$begingroup$
I am new to working on LDPC codes and have gotten stuck on this issue for some time. I am struggling on how to deal with parity check matrices that are not of full rank. I generate the parity check matrix using Gallager's construction (see example 1.14 http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf) and then attempt to get the result into systematic form, so that the matrix describes the information part and the parity part. When I do this however I am left with one or more all zero rows and to double check I checked the rank and it is indeed not full rank matrix.
The question I have is, what do I do when the parity check matrix starts out as not full rank? How do I get the systematic form and then the generator matrix? And what is the meaning of the parity check matrix not being full rank?
galois-theory coding-theory
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
$endgroup$
I am new to working on LDPC codes and have gotten stuck on this issue for some time. I am struggling on how to deal with parity check matrices that are not of full rank. I generate the parity check matrix using Gallager's construction (see example 1.14 http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf) and then attempt to get the result into systematic form, so that the matrix describes the information part and the parity part. When I do this however I am left with one or more all zero rows and to double check I checked the rank and it is indeed not full rank matrix.
The question I have is, what do I do when the parity check matrix starts out as not full rank? How do I get the systematic form and then the generator matrix? And what is the meaning of the parity check matrix not being full rank?
galois-theory coding-theory
galois-theory coding-theory
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
asked Dec 11 '18 at 13:48
BryanEhlersBryanEhlers
284
284
2
$begingroup$
If you construct this matrix in a random way, we can get a parity check matrix which is not full rank effectively. The redundant columns are useless for a code construction point of view. You can suppress them to get a systematic construction. But pay attention that this encoding method is not suitable for large sizes, as the obtained generating matrix is not sparse. For a decoding point a view, you can keep these redundant columns: the iterative decoding process is not optimal and you may loose in performance by suppressing these columns
$endgroup$
– Damien
Dec 11 '18 at 14:23
$begingroup$
@Damien That makes sense, thank you. The redundant columns are in some way representing a coded bit that it doesn't matter what its value is? Is this a correct way of thinking of the redundant columns?
$endgroup$
– BryanEhlers
Dec 11 '18 at 20:25
$begingroup$
I'm fairly sure that you are supposed to do the decoding with the original sparse check matrix. Linear dependencies among the check equations do create cycles in the Tanner graph, but unless they are relatively short, they won't disturb the decoding much. To have efficient encoding you do need to know the set of information positions at least. A high weight generator matrix may be bad for filling in the check positions. I'm afraid I'm not up to speed with all the related aspects for I have only ever seriously looked at LDPC codes with a little bit of extra structure.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 6:08
add a comment |
2
$begingroup$
If you construct this matrix in a random way, we can get a parity check matrix which is not full rank effectively. The redundant columns are useless for a code construction point of view. You can suppress them to get a systematic construction. But pay attention that this encoding method is not suitable for large sizes, as the obtained generating matrix is not sparse. For a decoding point a view, you can keep these redundant columns: the iterative decoding process is not optimal and you may loose in performance by suppressing these columns
$endgroup$
– Damien
Dec 11 '18 at 14:23
$begingroup$
@Damien That makes sense, thank you. The redundant columns are in some way representing a coded bit that it doesn't matter what its value is? Is this a correct way of thinking of the redundant columns?
$endgroup$
– BryanEhlers
Dec 11 '18 at 20:25
$begingroup$
I'm fairly sure that you are supposed to do the decoding with the original sparse check matrix. Linear dependencies among the check equations do create cycles in the Tanner graph, but unless they are relatively short, they won't disturb the decoding much. To have efficient encoding you do need to know the set of information positions at least. A high weight generator matrix may be bad for filling in the check positions. I'm afraid I'm not up to speed with all the related aspects for I have only ever seriously looked at LDPC codes with a little bit of extra structure.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 6:08
2
2
$begingroup$
If you construct this matrix in a random way, we can get a parity check matrix which is not full rank effectively. The redundant columns are useless for a code construction point of view. You can suppress them to get a systematic construction. But pay attention that this encoding method is not suitable for large sizes, as the obtained generating matrix is not sparse. For a decoding point a view, you can keep these redundant columns: the iterative decoding process is not optimal and you may loose in performance by suppressing these columns
$endgroup$
– Damien
Dec 11 '18 at 14:23
$begingroup$
If you construct this matrix in a random way, we can get a parity check matrix which is not full rank effectively. The redundant columns are useless for a code construction point of view. You can suppress them to get a systematic construction. But pay attention that this encoding method is not suitable for large sizes, as the obtained generating matrix is not sparse. For a decoding point a view, you can keep these redundant columns: the iterative decoding process is not optimal and you may loose in performance by suppressing these columns
$endgroup$
– Damien
Dec 11 '18 at 14:23
$begingroup$
@Damien That makes sense, thank you. The redundant columns are in some way representing a coded bit that it doesn't matter what its value is? Is this a correct way of thinking of the redundant columns?
$endgroup$
– BryanEhlers
Dec 11 '18 at 20:25
$begingroup$
@Damien That makes sense, thank you. The redundant columns are in some way representing a coded bit that it doesn't matter what its value is? Is this a correct way of thinking of the redundant columns?
$endgroup$
– BryanEhlers
Dec 11 '18 at 20:25
$begingroup$
I'm fairly sure that you are supposed to do the decoding with the original sparse check matrix. Linear dependencies among the check equations do create cycles in the Tanner graph, but unless they are relatively short, they won't disturb the decoding much. To have efficient encoding you do need to know the set of information positions at least. A high weight generator matrix may be bad for filling in the check positions. I'm afraid I'm not up to speed with all the related aspects for I have only ever seriously looked at LDPC codes with a little bit of extra structure.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 6:08
$begingroup$
I'm fairly sure that you are supposed to do the decoding with the original sparse check matrix. Linear dependencies among the check equations do create cycles in the Tanner graph, but unless they are relatively short, they won't disturb the decoding much. To have efficient encoding you do need to know the set of information positions at least. A high weight generator matrix may be bad for filling in the check positions. I'm afraid I'm not up to speed with all the related aspects for I have only ever seriously looked at LDPC codes with a little bit of extra structure.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 6:08
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3035299%2frank-deficient-ldpc-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3035299%2frank-deficient-ldpc-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
If you construct this matrix in a random way, we can get a parity check matrix which is not full rank effectively. The redundant columns are useless for a code construction point of view. You can suppress them to get a systematic construction. But pay attention that this encoding method is not suitable for large sizes, as the obtained generating matrix is not sparse. For a decoding point a view, you can keep these redundant columns: the iterative decoding process is not optimal and you may loose in performance by suppressing these columns
$endgroup$
– Damien
Dec 11 '18 at 14:23
$begingroup$
@Damien That makes sense, thank you. The redundant columns are in some way representing a coded bit that it doesn't matter what its value is? Is this a correct way of thinking of the redundant columns?
$endgroup$
– BryanEhlers
Dec 11 '18 at 20:25
$begingroup$
I'm fairly sure that you are supposed to do the decoding with the original sparse check matrix. Linear dependencies among the check equations do create cycles in the Tanner graph, but unless they are relatively short, they won't disturb the decoding much. To have efficient encoding you do need to know the set of information positions at least. A high weight generator matrix may be bad for filling in the check positions. I'm afraid I'm not up to speed with all the related aspects for I have only ever seriously looked at LDPC codes with a little bit of extra structure.
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 6:08