Hi, I read/looked at some PDF's on how LDPS work... So far I repeatedly see graphs... I think that's what the basic idea is about or maybe not at all ?!? For example Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 Bit 8 Bit 9 Bit 10 Check 1 = Bit 1 or Bit 2 or Bit 3 Check 2 = Bit 4 or Bit 5 or Bit 6 Check 3 = Bit 7 or Bit 8 or Bit 9 or Bit 10. I think the idea is that Check 1, Check 2 and Check 3 etc should always be zero. If a check is not zero then it is known that some bit must be 1. For example a fourth check could be Check 4 = Bit 2 or Bit 5. Suppose Bit 2 and Bit 5 were 0. Check 4 is then zero. Suppose Check 1 is one. Then that means bit 1 or bit 3 must be one... When having enough checks etc... it could be possible to figure out which bit was changed ?! Anyway how aobut some examples... Suppose there are 16 bits of data 1010-1111-0101-1011 How does one proceed to get the 'encoding' ? Anyway... I'll define my crazy method ;) I will have 4 parity bits. Check 1 = Bit 1 or Bit 3 or Bit 5 or Bit 7 or Bit 9 or Bit 11 or Bit 13 or Bit 15; Check 2 = Bit 2 or Bit 4 or Bit 6 or Bit 8 or Bit 10 or Bit 12 or Bit 14 or Bit 16; Check 3 = Bit 1 or Bit 4 or Bit 5 or Bit 8 or Bit 9 or Bit 12 or Bit 13 or Bit 16; Check 4 = Bit 3 or Bit 6 or Bit 7 or Bit 10 or Bit 11 or Bit 14; Now I'll do some calculations: But first some info: Bit data: 1010-1111-0101-1011 Bit 1 = 1 Bit 2 = 0 Bit 3 = 1 Bit 4 = 0 Bit 5 = 1 Bit 6 = 1 Bit 7 = 1 Bit 8 = 1 Bit 9 = 0 Bit 10 = 1 Bit 11 = 0 Bit 12 = 1 Bit 13 = 1 Bit 14 = 0 Bit 15 = 1 Bit 16 = 1 Check 1 = Bit 1 or Bit 3 or Bit 5 or Bit 7 or Bit 9 or Bit 11 or Bit 13 or Bit 15; Check 2 = Bit 2 or Bit 4 or Bit 6 or Bit 8 or Bit 10 or Bit 12 or Bit 14 or Bit 16; Check 3 = Bit 1 or Bit 4 or Bit 5 or Bit 8 or Bit 9 or Bit 12 or Bit 13 or Bit 16; Check 4 = Bit 3 or Bit 6 or Bit 7 or Bit 10 or Bit 11 or Bit 14; Check 1 = 1 or rest is not important Check 2 = Bit 6 = 1 rest is not important Check 3 = 1 Check 4 = 1 So my stupid crappy shit is pretty fucking stupid... since all checks are 1 :) So clearly I don't understand how LDPS works ;) Some clear examples would be great Bye, Skybuck.
How does LDPS work ? ;)
Started by ●July 2, 2004
Reply by ●July 2, 20042004-07-02
Skybuck Flying wrote:> Hi, > > I read/looked at some PDF's on how LDPS work...... I know you're frustrated, but please learn to contain your language. Instead of OR, try XOR and see what you can work out. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 2, 20042004-07-02
Well let's see my original idea was
8 Bits
4 Parity bits
Check bit X = bit A or bit B;
Check bit 1 = Bit 1 or Bit 2;
Check bit 2 = Bit 3 or Bit 4;
Check bit 3 = Bit 5 or Bit 6;
Check bit 4 = Bit 7 or Bit 8;
If Check Bit X is zero then
Begin Possibility 1:
A = 0;
B = 0;
End;
if Check Bit X is one then
Begin Possibility 1:
A = 1;
B = 0;
End Or
Begin Possibility 2:
A = 0;
B = 1;
End Or
Begin Possibility 3:
A = 1;
B = 1;
End;
Your idea is xor.
Check bit X = bit A or bit B;
Check bit 1 = Bit 1 xor Bit 2;
Check bit 2 = Bit 3 xor Bit 4;
Check bit 3 = Bit 5 xor Bit 6;
Check bit 4 = Bit 7 xor Bit 8;
If Check Bit X is zero then
Begin Possibility 1:
A = 0;
B = 0;
End OR
Begin Possibility 2:
A = 1;
B = 1;
End;
if Check Bit X is one then
Begin Possibility 1:
A = 1;
B = 0;
End Or
Begin Possibility 2:
A = 0;
B = 1;
End;
My idea's properties ;) ( OR )
1 Possibility for Check Bit X = 0; // 100% sure both are zero
// 100% sure both are
not one.
3 Possibility for Check Bit X = 1; // 33% A is one
// 33% B is one
// 33% A and B is one
Your idea properties ;) ( XOR )
2 Possibilities for Check Bit X = 0; // 50% sure both are zero
// 50% sure both are
one
2 Possibilities for Check Bit X = 1; // 50% sure A is zero
// 50% sure B is zero
Oh well let's see the 'and' idea
Check bit X = A and B
If Check Bit X is zero then
Begin Possibility 1:
A = 0;
B = 0;
End Or
Begin Possibility 2:
A = 0;
B = 1;
End Or
Begin Possibility 3:
A = 1;
B = 0;
End;
If Check Bit X is one then
Begin Possibility 1:
A = 1;
B = 1;
End;
3 Possibility for Check Bit X = 0; // 33% sure both are zero
// 33% sure A is zero
// 33% sure B is zero.
1 Possibility for Check Bit X = 1; // 100% sure both are one.
Hmmm... seeing these 100% sure things seems attractive to use.
I'll try this:
Check Bit 1 = Bit 1 xor Bit 2;
Check Bit 2 = Bit 3 xor Bit 4;
Check Bit 3 = Bit 5 xor Bit 6;
Check Bit 4 = Bit 7 xor Bit 8;
50% sure... <- pretty weak.
Check Bit 1 = Bit 1 or Bit 2 or Bit 3; // if zero then 100% sure all are
zero.
Check Bit 2 = Bit 2 or Bit 3 or Bit 4; // if zero then 100% sure all are
zero.
Check Bit 3 = Bit 4 or Bit 5 or Bit 6; // if zero then 100% sure all are
zero.
Check Bit 4 = Bit 6 or Bit 7 or Bit 8; // if zero then 100% sure all are
zero.
case 1:
original data = 0000 0000
check data = 0000
corrupted data = 0000 0001
to
corrupted data = 1111 1111
all detectable by
check data = 0000
case 2:
original data = 1111 1111
check data = 1111
At least one from check bit 1, check bit 2, check bit 3, check bit 4 was
set.
Example
Bit1, Bit 4, Bit 6
Many combinations possible.
Shitty.
Let's see what happens with multiple xor's
A xor B xor C = ( ( A xor B ) xor C )
0 0 0 = ( ( 0 ) xor 0 ) = 0
0 1 0 = ( ( 1 ) xor 0 ) = 1
1 0 0 = ( ( 1 ) xor 0 ) = 1
1 1 0 = ( ( 0 ) xor 0 ) = 0
0 0 1 = ( ( 0 ) xor 1 ) = 1
0 1 1 = ( ( 1 ) xor 1 ) = 0
1 0 1 = ( ( 1 ) xor 1 ) = 0
1 1 1 = ( ( 0 ) xor 1 ) = 1
Hmm the last one is a bit surprissing and unfortunate...
I was hoping xor could be used to detect only 1 set bit in a range of bits
;)
Oh well
Time to give up once again =D
Skybuck.
Reply by ●July 2, 20042004-07-02
Hmmm I can do what I want... Does bit range contain 1 bit ? Check Bit X = ( ( A xor B ) xor ( C xor D ) ) xor ( ( E xor F ) xor ( G xor H ) ); Hmmmm Check Bit X should now only be true if one of A,B,C,D,E,F,G,H is true. Skybuck.
Reply by ●July 2, 20042004-07-02
No, lol
Made a mistake..
a := true;
b := true;
c := false;
d := false;
e := true;
f := false;
g := false;
h := false;
if ( (A xor B) xor (C xor D) ) xor ( (E xor F) xor (G xor H) ) then
begin
ShowMessage('only one is true');
end;
if A and B are true and one of the others is true it will still work ;)
Hmm tricky stuff =D
Reply by ●July 2, 20042004-07-02
Skybuck Flying wrote: ( ( A xor B ) xor ( C xor D ) ) xor ( ( E xor F ) xor ( G xor H ) )= A XOR (B XOR (C XOR (D XOR (E XOR (F XOR (G XOR H)))))). On other words, parity. If I remember correctly, it's a matter od checking the parity of distributed sets, some of which include parity bits.> HmmmmJerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 3, 20042004-07-03
On Sat, 3 Jul 2004 02:11:15 +0200, "Skybuck Flying" <nospam@hotmail.com> wrote:>Hmmm > >I can do what I want... > >Does bit range contain 1 bit ? > >Check Bit X = ( ( A xor B ) xor ( C xor D ) ) xor ( ( E xor F ) xor ( G xor >H ) ); > >Hmmmm > >Check Bit X should now only be true if one of A,B,C,D,E,F,G,H is true.In your next post you use a Pascal code snippet. Let me see if I remember my Pascal: var int onescount; begin onescount := 0; if (a) then onescount := onescount + 1; if (b) then onescount := onescount + 1; if (c) then onescount := onescount + 1; if (d) then onescount := onescount + 1; if (e) then onescount := onescount + 1; if (f) then onescount := onescount + 1; if (g) then onescount := onescount + 1; if (h) then onescount := onescount + 1; (* Thank God (or was it Alan Kay?) for copy-and-paste. *) x := false; if (onescound = 1) then x := true; end.>Skybuck.BTW, what is LDPS? I googled around and found something on LDPC, Low Density Parity Check. Regardless, it doesn't look much like DSP - maybe you should ask on a more appropriate newsgroup.
Reply by ●July 3, 20042004-07-03
"Ben Bradley" <ben_nospam_bradley@mindspring.com> wrote in message news:vo2ce09oa0dvnn0482bn6cgonbub1uu6a2@4ax.com...> On Sat, 3 Jul 2004 02:11:15 +0200, "Skybuck Flying" > <nospam@hotmail.com> wrote: > > >Hmmm > > > >I can do what I want... > > > >Does bit range contain 1 bit ? > > > >Check Bit X = ( ( A xor B ) xor ( C xor D ) ) xor ( ( E xor F ) xor ( Gxor> >H ) ); > > > >Hmmmm > > > >Check Bit X should now only be true if one of A,B,C,D,E,F,G,H is true. > > In your next post you use a Pascal code snippet. Let me see if I > remember my Pascal: > > var int onescount; > begin > onescount := 0; > > if (a) then onescount := onescount + 1; > if (b) then onescount := onescount + 1; > if (c) then onescount := onescount + 1; > if (d) then onescount := onescount + 1; > if (e) then onescount := onescount + 1; > if (f) then onescount := onescount + 1; > if (g) then onescount := onescount + 1; > if (h) then onescount := onescount + 1; > > (* Thank God (or was it Alan Kay?) for copy-and-paste. *) > > x := false; > if (onescound = 1) then x := true; > > end. > > >Skybuck. > > BTW, what is LDPS? I googled around and found something on LDPC, > Low Density Parity Check. Regardless, it doesn't look much like DSP - > maybe you should ask on a more appropriate newsgroup.Oh shit, I ment LDPC :) What would be a more appropriate newsgroup ?
Reply by ●July 3, 20042004-07-03
"Jerry Avins" <jya@ieee.org> wrote in message news:40e60dfc$0$23327$61fed72c@news.rcn.com...> Skybuck Flying wrote: > ( ( A xor B ) xor ( C xor D ) ) xor ( ( E xor F ) xor ( G xor H ) )= > > A XOR (B XOR (C XOR (D XOR (E XOR (F XOR (G XOR H)))))). On other words, > parity. If I remember correctly, it's a matter od checking the parity of > distributed sets, some of which include parity bits.Euhm I think this code will return a 1 when it's oneven and 0 when it's even. I always think my code works like that. That's indeed a parity bit... But that's not what I wanted... I wanted to detect if only 1 bit was set... It probably could be done with or, and, xor, not, etc... but would take too much code. Counting the bits is probably shorter/faster/better. Anyway... sigh... This thread was supposed to be about LDPC ;)
Reply by ●July 3, 20042004-07-03
Well
I would like to keep things as simple as possible when it comes to LDPC's
Unfortunately it seems all these PDF's make things 100x times more complex
than it really is...
Except maybe for the probability calculations....
But first the general concept would be nice to know.
I think I am beginning to understand the concept/talk ;)
1. The data that needs be transmitted is called a vector. Let's say vector D
for data ;)
2. Another concept is parity. Parity means if a couple of bits are even or
uneven. The LDPC concept is to look at a few data bits and then determine if
these are even or uneven. For example Parity Bit 1 = ( ( (Bit 1 xor Bit 2)
xor Bit 3) xor Bit 4); // this will return zero for even or one for uneven.
3. The talk is about a Sparse Or Dense (this is all blablabla since it
probably doesn't matter that much to grasp the basic concept;)) Parity
MATRIX.
The Parity Matrix specifies which bit's need to be checked for parity for
each row. The number of rows of the Parity Matrix is the number of Parity
Bits. This can vary depending on how much Parity Bits one wants... The
number of columns should match the number of (total) bits in the data.
For example
Parity Matrix ( I think they call it Matrix H ;) )
Data Bit 1 Data Bit 2 Data Bit 3 Data
Bit 4 Data Bit 5 ( Column )
Parity Bit 1 (Row) 1 0 0
1 0
Parity Bit 2 (Row) 0 1 0
0 1
Parity Bit 3 (Row) 0 0 1
0 0
I don't like matrices... I don't even have code to multiply them... however
in this case it could be simple...
Anyway must documents don't like having to multiply matrices etc... so the
same Parity Matrix can be written as a bunch
of 'equations' or a graph or something ;)
Like so:
Parity Bit 1 = Data Bit 1 xor Data Bit 4;
Parity Bit 2 = Data Bit 2 xor Data Bit 5;
Parity Bit 3 = Data Bit 3;
Ok that's how much I understand up to this point ;)
They also talk about some generator matrix G I dont know what's that
about...
4. The next step could be to transmit the 5 data bits + the 3 parity bits...
which happens to be 8 bits ;)
That's as far as the Encoding steps go I guess.
Let's make an example
Data bits: 12345 index ;)
Data bits: 10101 data ;)
Parity Bit 1 = 1 xor 0 = 1;
Parity Bit 2 = 0 xor 1 = 1;
Parity Bit 3 = 1
Transmitted bits = Data Bit + Parity Bits
Transmitted bits = 10101 + 111;
Now some noise occurs:
Transmitted bits = 10101111;
Noise bits = 00010100; // every one is a bit flip, in my case ;)
Received bits = 10111011;
Well I am not sure how the decoding would go so I ll just make something
up...
The decoder knows the parity equations as well.
So let's calculate the parity bits based on the received bits
Received bits = 12345678; // index
Received bits = 10111011; // data
Parity Bit 1 = Data Bit 1 xor Data Bit 4;
Parity Bit 2 = Data Bit 2 xor Data Bit 5;
Parity Bit 3 = Data Bit 3;
Calculated Parity Bit 1 = 1 xor 1 = 0;
Calculated Parity Bit 2 = 0 xor 1 = 1;
Calculated Parity Bit 3 = 1 xor;
Hmm... the funny things is
The calculated Parity Bits match the Received Parity Bits.
No error detected ;)
Funnnnnny :)
Bye,
Skybuck.
