FORM - 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10; rule 13)
SYSTEMS FOR DECODING LOW DENSITY PARITY CHECK CODES USING PERFECT DIFFERENCE NETWORKS (PDNs)
TATA CONSULTANCY SERVICES LIMITED,
an Indian Company of Nirmal Building, 9th Floor, Nariman Point, Mumbai - 400 021,
Maharashtra, India.
THE FOLLOWING SPECIFICATION PARTICULARLY DESCRIBES THE INVENTION AND THE MANNER IN WHICH IT IS TO BE PERFORMED

Field of the Invention:
This invention relates to the field of communication.
Particularly, this invention relates-to error correcting means in the field of
transmission and reception.
Still particularly, this invention relates to systems for decoding Low Density Parity Check codes using Perfect Difference Networks (PDNs).
Background of the Invention:
Decoding of Low Density Parity Check (LDPC) codes involves variable node processing and check node processing and subsequent exchange of soft information from variable nodes (bit nodes) to check nodes on a factor graph framework. Typically, each node is a processing element. Generally, decoder architecture is code specific and is designed with a view to speed up communication between nodes by reducing or avoiding conflicts. Decoding LDPC codes is communication intensive as messages are exchanged frequently between variable nodes and check nodes.
This necessitates an efficient inter-connection network between the computing nodes.
PDNs are based on perfect difference sets (PDS), also known as Singer difference sets, which are obtained using 2-D projective geometry (PG) constructs over a prime p or prime power p' (/ being a positive integer). The diameter of such networks is 2. Using this network, one-to-one, one-to-all, all-to-all and personalized communications can be carried out in 2p time steps, if

each node involved is having single port facility; or in 2 time steps if it has multi-port facility.
During each time step, communication among nodes takes place without any conflict (i.e. clash-free). Further, irrespective of the number of nodes involved, the graph relevant to the PDN is sparse and has a constant diameter of 2 (signifying a maximum of two hops to reach from a node to any other node). Having both these features in a graph is rather counter-intuitive. AH these properties make PDNs a very powerful and useful architecture for interconnections.
The above discussion calls for a strategy to map any arbitrary LDPC code onto a PDN which is easily scalable and reconfigurable.
Prior Art:
Any LDPC decoder architecture has a shuffle network which caters for the exchange of soft information between variable nodes and check nodes. Decoders for cyclic LDPC codes can involve a very simple shuffle network (inter-connecting architecture). But it can become really cumbersome for a non-cyclic LDPC code. In order to account for both cyclic and non-cyclic LDPC codes (regular or irregular), and hence to have a universal shuffle network, there is a need for a PDN'based inter-cortfiection architecture, which efficiently manages the connectivity among the nodes without any clashes.
Summary of the Invention:
According to this invention, there is provided a system for sending messages and for clash free decoding of Lower Density Parity Check (LDPC) codes,

between a set of variable node elements and a set of check node elements, for a set of interconnected processing node elements with a fixed interconnect architecture, said system comprises:
- code generation means adapted to provide LDPC codes;
- Perfect Difference Network (PDN) building means adapted to build Perfect Difference Networks in order to provide said fixed interconnect architecture;
- first mapping means adapted to map said LDPC code on a built PDN having node elements of pre-fixed size;
- second mapping means adapted to map factor graph based signal processing algorithms on said built PDN for facilitating reusability of said interconnected processing node elements; and
- sum-product algorithm based iterative decoding means adapted to iteratively decode said messages by providing a soft decision message passing algorithm means to accept the probability of each received bit as input.
Typically, said Perfect Difference Network building means includes means to build Perfect Difference Networks based on Perfect Difference Sets.
Preferably, said Perfect Difference Network building means includes means to build Perfect Difference Networks based on 2-dimensional Projective Geometry constructs over prime elements.
Typically, said sum-product algorithm based iterative decoding means includes Log Likelihood Ratio generation means adapted to generate probability values for decoding as Log Likelihood Ratio values.

Typically, said sum-product algorithm based iterative decoding means includes initialization means adapted to provide an initialisation Log Likelihood Ratio value based on communication channel used for said system.
Typically, said system includes iteration limiting means adapted to provide limits for said iterative decoding means.
Typically, said sum-product algorithm based iterative decoding means includes iteration limiting means adapted to provide limits for iterative decoding means and further includes iteration means adapted to iteratively pass said messages between said set of variable node elements and said set of check node elements until said iterative limit is valid.
Brief Description of the Accompanying Drawings:
The invention will now be described in relation to the accompanying drawings,
in which:
Figure 1. illustrates a PDN with n = 13 nodes based on PDS {0, 1, 3, 9};
Figure 2 illustrates an example of routing in a PDN with n = 13 nodes;
Figure 3 illustrates Phase 1 of one to all broadcasting in a PDN with n =13
nodes;
Figure 4 illustrates Phase 2, step 1 on one to all broadcasting in a PDN with n
=13 nodes;
Figure 5 illustrates Phase 2, step 2 on one to all broadcasting in a PDN with n =13 nodes;

Figure 6 illustrates Phase 2, step 3 on one to all broadcasting in a PDN with n =13 nodes; and
Figure 7 illustrates end of Phase 2 of one to all broadcasting in a PDN with n = 13 nodes.
Detailed Description of the Accompanying Drawings:
According to this invention, there is envisaged a generic system for clash free decoding of Low density parity check codes (LDPC).
Typically, this system includes a reconfigurable fully-parallel/semi-parallel decoding architecture for any LDPC codes using perfect difference networks (PDN).
The system consists of a set of interconnected processing nodes with a fixed interconnect architecture based on PDN. The processing nodes of the system are mapped to the check nodes and variables nodes of the LDPC decoder. The innovative aspect of the system is in mapping the decoder architecture of any arbitrary LDPC code to this PDN system without requiring any change in the physical interconnections or number of nodes ensuring a clash free parallel operation.
In accordance with an embodiment of this invention, there is provided a generic fully-parallel/semi-parallel architecture for clash-free decoding of PG based LDPC codes.

In accordance with another embodiment of this invention there is provided a reconfigurable fully-parallel/semi-parallel clash-free architecture for any LDPC codes using PDN.
In accordance with yet another embodiment of this invention, there is provided a first mapping means adapted for mapping of any arbitrary length LDPC code on a PDN of fixed size (fully-parallel/semi-parallel clash-free architecture).
In accordance with still another embodiment of this invention, there is provided a second mapping means for Mapping of factor graph based signal processing algorithms on PDN. For instance, the decoding and other related signal processing algorithms for any communication receiver can be mapped to PDN based architectures which can facilitate the reusability of processing blocks.
In accordance with an additional embodiment of this invention, there is provided a means adapted for use of a reconfigurable system architecture for arbitrary LDPC clash free decoding for future-proof wireless communication chips towards any change in the LDPC codes used in respective standard without needing the refabrication of-the chip.
In accordance with an additional embodiment of this invention, there is provided a code generation means adapted to provide Low Density Party Check codes. Low Density Parity Check (LDPC) codes have emerged as very powerful error control codes with performance approaching capacity limits. LDPC codes are linear block codes originally proposed by Gallager in the early 1960s. Their parity check matrix is sparse having low density of 'one' entries. Good performance of LDPC codes can be achieved with a proper choice of

code and decoding algorithm. The class of decoding algorithms used to decode LDPC codes are collectively termed message-passing algorithms since their operation can be explained by the'passing of messages along the edge of a Tanner graph. To be more specific, each node is carrying out the computation by obtaining the information from its neighbors (local computation). Each Tanner graph node works in isolation, only having access to the information contained in the messages on the edges connected to it. The message-passing algorithms are also known as iterative decoding algorithms as the messages pass back and forward between the bit and check nodes iteratively until a result is achieved (or the process halted). Different message-passing algorithms are named for the type of messages passed or for the type of operation performed at the nodes. In some algorithms, such as bit-flipping decoding, the messages are binary (hard) and in others, such as belief propagation decoding, the messages are probabilities (soft) which represent a level of belief about the value of the codeword bits. It is often convenient to represent probability values as log likelihood ratios (LLR), and when this is done belief propagation decoding is often called sum-product decoding since the use of LLRs allows the calculations at the bit and check nodes to be computed using only sum and product operations.
In accordance with yet an additional embodiment of this invention there is provided a sum-product algorithm (SPA) based means which is a soft decision message-passing algorithm which accepts the probability of each received bit as input. The input bit probabilities are called the a priori probabilities for the received bits because they are known in advance before running the LDPC decoder. A priori probabilities use the knowledge of the channel properties. The bit probabilities returned by the decoder are called the a posteriori probabilities. In the case of sum-product decoding these probabilities are

expressed as LLRs, mentioned earlier. For a binary variable x, if p is the probability of the bit being 1, then (1ip) is the probability of it being 0. The probabilities can be represented as LLRs by

The sign of L(x) is the hard decision and the magnitude jL(x)j is the reliability of the decision. The aim of sum-product decoding is to compute the a posteriori probability (APP) for each codeword bit, P1 = Prob{ct - l/N}, which
is the probability that the t codeword bit is a 1, conditional on the event Y
that all parity check constraints are satisfied. The intrinsic or a priori
probability , is the original bit probability independent of knowledge of
the code constraints, and the extrinsic probability represents what has
been learnt from the event N.
Consider 'm' n parity check matrix H having'n' variable nodes and 'm' check

nodes.
where hu ( GP{2).
Let A be a matrix that gives addresses of 'ones' in H column-wise, where each row of A represents the parity-check equations which check on the/ -bit of the code, forj = 1; 2; 3;...; n.


where, j gives the number of ' ones' jth column of H. Let B be a matrix that
gives addresses of 'ones' in Hrow-wise, where each row of B represents the set
of bits in the Ith parity-check equation, for i = 1; 2; 3; ;m.

where PI gives the number of 'ones' in ih row of H. Hence, A and B define the connections in the corresponding Tanner Graph for the given parity-check matrix H. The steps involved in SPA are described below: Initialization

is the intrinsic (a priori) channel LLR value which can be obtained depending
on the channel and is the information sent by a variable nodey to
its connected check node(s) given in A(j; i),

E(1)i.B(1-j) = 0. i= 1,2 in & j= 1,2 Pi (2)
Ei.B(1-j) is the extrinsic LLR value passed from check node i to its
connected variable node(s) given in B(i,J).
This completes the initialization of the SPA. The next step is to pass messages
between variable and check nodes iteratively until a valid codeword is found or
the number of iterations exceed a pre-defined value.
Iteration : Let Imax be the maximum number of iterations. Then, for iteration
counter / = 1; 2;:: :; Imax, do the following:
Step 1 : Check node update rule

here,
/= 1; 2; ; m:
/=l/2; ;'Ai:

Step 2 : Codeword Test

o test, the intrinsic and extrinsic probabilities for each bit are combined to give the total LLR (Lj). For each bit a hard decision is made as follows:


hj is the jth column of the parity-check matrix H) or if the maximum number of allowed iterations have been completed (i.e. / = Imax), the algorithm terminates.
Step 3 : Variable node update rule

where,j= 1; 2; ; n & / - 1; 2; ; j .
Return to Step 1.
The emphasis of this report is on the elegant mapping of the SPA or in general
any message passing algorithm to the perfect difference network.
In accordance with still an additional embodiment of this invention, there is provided a means for Perfect Difference Networks. As mentioned earlier, PDN networks are based on Perfect Difference Sets (PDS). Singer has given a systematic procedure for constructing PDS using 2-dimensional Projective Geometry (PG) constructs over prime p or pt, where Ms a positive integer. A PDS can be defined as:
Perfect Difference Sets (PDS): Let n be a positive integer. A set D of positive integers is called a perfect difference set (PDS) of order/?, if - D has exactly p + 1 elements.


- any integer from {\; 2; 3; ; p 2+p} can be written in a unique way
as
(I - d mod p2 + p + 1 with d.d' € D. (7)
Remark. The symbol "mod' is used in two ways. Firstly, a mod p denotes the least Tionnegative remainder when a is divided by p. Secondly, a = b modp ('a is congruent to b modulo/?') means that a - b is divisible by p, or in other words, a mod p = b mod p.
For a given p there are totallyp2 +p + 1 such sets and each such set has
p+\ elements. Similarly for a given pt, there arep2H-p/+l PDS and each such
set hasp' + 1 elements. Consider the PDS of the form {0, I, 52, S3, ,Sp)
with Si for i= 2 to p and call it a normal PD set. The PDS lead to the design of efficient and robust interconnection networks which in the literature is called the Perfect Difference Networks (PDNs).
Consider the normal PD set {0; 1; 52; 53; ; Spj. This is called normal
PD set of order p. It can be sued to construct a direct interconnection network with N = p2+p+\ nodes, numbered from 0 to N - 1. Node i is connected to
nodes i± 1 and i±Sj mod N for 2 < j < p . This connectivity leads to
a chordal ring of in-and out-degree d=2p and diameter D-2. This is because
it is assumed for each link (/; j), the reverse link (J; i) also exists. The network
leads to an undirected simple (without self loops and multiple edges) k-regular
graph with k = 2p.
Examples of normal PDS of order p forp = 2 to 13 are given below in Table
1.

Based on the definition of PDN, it can be described a network for p = 3. For this network,
N =p2+p + l = 13 and d = 2. p = 2. 3 = 6. The normal PDS for p = 3 is {0, 1, 3, 9} (see Table 1).
Thus S2 = 3 and S3 = 9. The interconnections are described by the relation (i ±1) mod (p2 +p + 1) and (/ ± 5/) mod (p2 +p + 1). Hence, forp = 3, the interconnections are (i± 1) mod (p +p + 1), (i 3) mod (p + p + 1) and (i ± 9) mod (p +p + 1). The connections are given in Table 2.
Pictorially the interconnection is depicted in Figure 1 of the accompanying
drawings. Let G{V;E) be the graph of the above PD network.
\V\ = no. of vertices =p2 +p +1 = 13
It is a k-regular graph with k=2.p=6. Thus,

In the terminology of chordal rings the links connecting consecutive nodes i and i + 1 are ring links, while those-connecting non-consecutive nodes i and i + Sj are referred to as the forward skip link of node i and backward skip link of node i + Sj . Similarly the ring link between nodes i and z + 1 is a forward ring link for i while a backward ring link for (i + 1).
An example of PG(2; p) for p = 3 is shown in Figure 1 of the accompanying
drawings.

Table 1: Normal PDS of order p

p v PDS of order p in normal form
2 i 0, 1, 3
3 13 0. 1. 3. 9
5 31 0. 1. 3. 8, 12, 18
7 57 0. 1, 3, 13, 32, 36, 43, 52
11 133 0, L 3. 12, 20, 34, 38, 81, 88, 94, 104, 109
13 183 0, 1. 3. 16. 23. 28: 42, 76, 82, 86., 119, 137, 154, 175
Table 2: Interconnections in a PDN for p = 3, N = 13

/ {/ + 1) (? - 1) u + s2) (i + So) (t + 53) (i → 53)
0 0 → 1 0→ 12 0→3 0 →10 0→9 0→4
1 1 → 2 1 →0 1 → 4 l→ 11 1→10 1→ 5
2 2 → 3 2→ 1 2→5 2 → 12 2 →11 2→ 6
3 3 → 4 3→2 3→6 3→0 3→ 12 3→ 7
.1 -J. → 5 4 → 3 4→ 7 4→ 1 4→0 4→8
.'i 5 → 0 5 → 4 5 → 8 5→2 5→ 1 5 → 9
0 G→ 7 6 → 5 6 →9 6→3 6→2 6→10
i 7 → 8 7→6 7→10 7→4 7→3 7 → 11
8 8→9 8→7 S→11 8→5 8→4 8→ 12
0 9 → 10 9 → 8 9 → 12 9→6 9 → 5 9 → 0
10 J 0→ 11 10 → 9 10 → 0 10 → 7 10→ 6 10 → 1
11 11 →12 11 →10 11 →h 1 11 → 8 11→ 7 11 →2
12 12→ 0 12 →11 12→2 12 → 9 12→8 12 →3
Number of lines =p2+p + 1 = 13 Number of points =p2+p + 1 = 13 Number of points on any line =p + 1 =4
This is a !- ~' ''" y ' block design with v = 13, k = 4 and ~~ .
Normal PDS = {0; 1; 52; S3j = {0; 1; 3; 9; Degree of PDN formed = 2p = 6.


Total No. of Connections =

The graph G(V;E) of PDN is a k-regular graph with k= 6,1V]- no. of points =
13 and LEI = no. of connections = 39.
There are two important operations worth considering on the network or the
mapping of message passing edge can be viewed in terms of these two
algorithms.
Algorithm 1 : Routing in a PDN
Routing from a source node x to destination node y is tantamount to
determining an intermediate node ksuch that k-x = Si and k-y~ Sjfor some
pair of elements S, and Sj in PDS. This is always possible because given the
pair (x; y) there is always a unique node which has direct links to nodes i and j.
(v k λ) This uniqueness is because of the fact that the PDN is a ' b' ' block design
withλ =1.
For example in Figure 2 of the accompanying drawings, source node 1 wants to have a routing with destination node 7. Here x = 1 andy = 7. For the pair (x, y) = (I, 7) there is a node namely node 11 through which link can be established between nodes 1 and 7.
Algorithm 2: Broadcasting in a PDN
Broadcasting in a PDN is a 2-phase process given that network diameter is 2.
Assume the single-port communication model where a node can be linked to
only one of its neighbours in each time step. In the first phase, the initiating
node x sends broadcast message to its p neighbours in p time steps. So at the
end of p time steps in the first phase p+\ nodes including the initiator have
broadcast message. This set of transmissions can be mathematically written as
x - x + Si for i = 1/2; ; p.

In the second phase, each node y that already has broadcast message (including the initiator) sends message to nodes y - Sj except for the node from which the broadcast message was received. In this step, x sends broadcast message to p nodes and each of the p intermediate nodes sends broadcast message to p\ 1 other nodes. Thus a total of p2+p nodes receive broadcast message. All these transmissions of second phase can be done in p time steps. Thus broadcasting in a PDN is done in 2p time steps.
Let us assume that in Figure 3 of the accompanying drawings, node 3 wants to
broadcast message. So x = 3 is the initiator node. In the first phase, broadcast
message is sent to nodes x+Si for i = 1; 2; : : : ; p. The normal PDS = {0; 1;
S2; S3} = {Q; 1; 3; 9}. Thus, the nodes which receive message from node 3
during the first phase are:
x +SI =x+1=3 + 1=4
x + S2=x + 3=3+3 = 6
x + S3=x + 9 = 3 + 9=12
The first phase of operations are completed mp = 3 time steps and nodes 3, 4,
6 and 12 are having the broadcast nTessage.
In the second phase, nodes y = 3 sends broadcast message to y - Sj for/ = 1; 2
and 3 in 3 time steps. The nodes which receive message from node 3 during
second phase are
y-S\ =y- 1=3 -7 =2
y-s2=y-3 = 3-3 = 0
y - S3 =y - 9 = 3 - 9 = -6 = 7 mod 13
So nodes 0, 2, and 7 receive broadcast message from node 3 during second
phase.

In parallel, nodes 4, 6 and 12 send broadcast message to nodes y - Sj, where y
4; 6; 12 and y = 1; 2 and 3. For y = 4, the nodes which receive broadcast message are y-S\ =y- 1 =4- 1 = 3 y - 52 =y - 3 = 4 - 3 = 1 j; - 53 =.y - 9 = 4 - 9 = -5 = 8 mod 13 Tory = 6, the nodes which receive broadcast message are y-S\=y-1=6-\=5 y-S2=y-3 = 6-3=3 y - S3 =y - 9 = 6 - 9 = -3 = 10 mod 13 Fory= 12, the nodes which receive broadcast message are y-S] =y- 1 = 12- 1 = 11 ^-52=y-3 = 12-3 = 9 7-53=y-9 = 12-9 = 3
N.B. Node 3 should not be considered in all the above cases as it is the initiator of the message.
So the set which receives the broadcast message is {4; 6; 12} during first phase; while {2; 0; 7}, {\; 8}, {5; 10} and {l\; 9} are the sets that receive broadcast message during second phase. Union of sets belonging to first phase and second phase is {0; 1; 2; 4; 5; 6; 7; 8; 9; 10; 11; 12} with size of the set = 32+3 = 12.
The concepts of broadcasting can be generalized to all to all broadcasts and all to all personalized communication.. The model for both cases assumes that a node has facility to receive and transmit messages simultaneously. The schemes are explained through examples w.r.t Figure 1 of the accompanying drawings.

In an all to all broadcast scenario, the contents of various nodes after the first phase of operations is given below. The first phase operations are transmission of the form x → x +Si for xЄ {0,1. 2,. . . , 12} and i= 1; 2; 3. N.B. An element / of any set implies broadcast message from node f.
0 — {0,12, 10, 4} 1— {1,0,11,5} 2-{2,1,12,6}
3— {3,2,0,7}
4— {4,3,1,8}
5— {5,4,2,9} 6 — {6,5,3,10}
7— {7,6,4,11}
8— {8,7,5,12}
9— {9,8,6,0}
10— {10,9,7,1}
11 — {11,10,8,2}
12— {12,11,9,3}
During the second phase, the operations are of the form y →y - S j where
y Є{0.1..2....,12}andj=1,2and3

During time step 1, y — y-S1 transmissions take place for
y Є {0.1..2...... 12} all in parallel, without conflicts. Contents of nodes 0
to 12 after time step 1 are shown below.

0— {0.12,10,4,1,11,5}
1— {l,0,ll,5, 2,12,6}
2— {2,1.12.6,3,0,7}
3— {3.2,0,7,4,1,8}
4— {4,3.1,8,5,2,9}
5— {5.4,2,9,6,3,10}
6— {6.5,3,10,7,4,11}
7— {7,6,4,11,8,5,12}
8— {8,7,5,12,9,6,0}
9— {9,8,6,0,10,7,1} 10— {10/9,7,1,11,8,2} 11— {11.10,8,2,12,9,3} 12— {12,11,9,3,0,10,4}
During time step 2, y — y—S2 transmissions take place for
y Є {0.1..2...... 12} all in parallel, without conflicts. Contents of nodes 0

to 12 after time step 1 are shown below.

0 → {0. 12,10,4,1,11,5,3,2, 7,8}
1 → {1.0,11,5,2,12,6,4,3,8,9}
2 → {2.1,12.6,3,0,7,5.4,9,10}
3→{3,2,0,7,4,1,8,6,5,10,11} 4→{4,3,1,8,5,2,9,7,6,11,12} 5→ {5,4,2,9,6,3,10,8,7,12,0}
6 → {6,5,3,10, 7,4,11, 9,8,0,1}
7 → {7. 6.4; 11.8.5,12.10.9.1,2}
8→{8,7,5.12,9,6,0,11,10,2,3}
9→{9,8.6.0,10,7,1,12,11,3,4}
10→{10,9.7.1,11.8,2,0,12,4,5}
11 → {11,10,8,2.12,9,3,1,0,5.6}
12 → {12.11,9,3,0,10, 4,2,1,6, 7}
During time step 3, y→y→S3 transmissions take place fory Є {0.1.2........ 12 }all the parallel without conflicts. Contents of nodes 0 to 12 after time step 3 aresnown below.

0 →{0,12,10,4,1,11., 5, 3, 2. 7,8,9,6}
1→ {1,0,1,1, 5,2, 12,6, 4, 3,8,9,10,7}
2 → (2:1.12.6.3:0, 7, 5,4,9,10,11,8}
3 → {3, 2, 0,7,4,1,8,6, 5,10,11,12,9}
4 -→ {4.3,1. S, 5. 2,9,7,6, 11,12, 0,10}
5 → (5, 4. 2,9,6, 3,10,8,7,12,0,1,11}
6 → {6,5. 3,10, 7,4,11.9,8, 0,1,2,12}
7 → {7, 6, 4,11.8,5,12,10,9,1,2, 3, 0}
8→ {8. 7. 5,12. 9,6, 0,11,10,2,3,4,1}
9 → {9.8. 6. 0,10. 7,1,12,11,3, 4,5,2}
10 → {10,9. 7. L 11,8,2,0,12,4, 5,6,3}
11 → {11,10. 8, 2,12, 9,3,1,0, 5,6,7,4}
12 →{12.1L 9. 3,0,10,4,2,1,6, 7,8,5}
After/? = 3 steps during second phase all the nodes have contents from rest ofp +p nodes. Thus all to all broadcast can be completed in 2p steps with the following assumptions:
Typically, each node has a single port. Each node has facility to transmit and receive simultaneously (full duplex).
p.v (i)= { i— 11a1, i— 1a1 ..1— i— 1ai— 1..1— i+1a2+1....i— p2+pap2+p
fori = 0.1.2 p2+p
In
the case of all to all personalized communication, a personalized message
set is represented as shown above. An element of the set i— jaj implies
personalized message from node i to node j, i 6=j. Like all to all broadcast, all to all personalized communication can be completed in 2p steps. All the steps remain same as that for all to all broadcast algorithm except that broadcast

message / of the source node i is replaced by the set PM(i) of personalized messages.
In accordance with yet an additional embodiment of this invention, there is provided strategy means for providing a strategy for mapping the variable nodes and check nodes of any general LDPC codes using PDN for processing SPA in an efficient way.
Typically, for One-to-one mapping, there is provided a generic clash free
architecture for SPA. It is assumed that each processor (Pj) is mapped to only
one variable node or check node. The steps for SPA decoding using PDN is
given below.
Step 1 : ALL-to-ALL Broadcast
Initially, each processor Pj will contain the a priori channel LLR value /,.
Contents of processor Pj after Step 1:
It is assumed that the number of check nodes m is not greater than the number of variable nodes n. The contents of processors after Initialization and Check node update rule of SPA are given below:

Initialization
Ciifc.k node update rule


where, i = 1, 2...., m . j = 1,2,..., /?, & 0 < /c < (n — m).
Step 2 : ALL-to-ALL Personalized Communication The personalized messages PM(k + i) sent by processor Pk+i in ALL-to-ALL personalized communication is :

where. i = 1,2. ... ,m , j = 1.2,....p1 & 0 < k < (n - m). Contents of processor Pj after Step 2:
P; : E(1)A(j.1).j. . j— 1,2,.. .,n &: i=l,2,. ..,λj-. Each processor Pj will calculate the total LLR (Z,-):
Pf.L;. i = 1.2 n & i= 1.2 A,-.
Step 3 : ALL-to-ALL Broadcast The contents of processor Pj after Step 3:
'PJ:LJ. j = l,2,..,n &: i = 1,2,...,λj-.
Typically, Codeword Test can be done at any processor Pj. If conditions are not satisfied, Variable node update rule is carried out. The contents of each processor Pj is given below.

Variable node update rule

Step 4: ALL-to-ALL Personalized Communication
The personalized messages PM(j) sent by processor Pj in ALL-to-ALL
personalized communication:

' where j = 1.2 11 . i = 1,2...... \j & 0 < k < (n - m), Contents of
procassor Pt.+i after Step 4:
Pl.-+i--Tj%[iJr i = 1.2,...sm & j = l,2s....pt,
Return to Check node update rule of Step 1.
This completes one iteration of SPA decoding. The given steps can be repeated until valid codeword is found or the iterations reach a pre-defined maximum value. An important observation" is that the above given architecture is applicable for any irregular or regular LDPC codes. Also, it may be noted that this scheme works even when one processor is mapped to multiple variable nodes or check nodes.
Typically, for One-to-many mapping, distribution of check node processing and variable node processing on to processor nodes depends on the number of processor nodes at disposal and the length of the LDPC codes, which in turn defines number of check nodes and variable nodes. This implies each processor node may own more than one check/variable nodes. The computational load on each processor node depends on the number of check nodes and variable nodes and respective degree of each of these nodes. Communication load is also

dictated by the same parameter which influences computational load. Optimum strategy should see that computation loads and communication loads are well balanced. This makes the strategy code specific for a given number of processors at disposal.
Format of Personalized Packet for one-to-many mapping: Typically there is
provided a description of constructing personalized packet by a processing
node soon after check node processing. It is assumed that the processor serves
•j
multiple check nodes. The processor nodes are numbered from 0 to ' . Ck
and Vk denote the set of check nodes and variable nodes owned by the
processor node k. For this purpose, in the expression for check node LLR given

I1 "-1" ' identifies the processor node, iЄ Ck identifies the set of check nodes owned by the processor node k and B(i, j) identifies the set of variable nodes that are neighbors to check node /. The check node personalized package constructed by processor k has k as header followed by the set of check node LLR data tagged with source/destination node
information. Similar explanation holds good for the construction of personalized package after variable node processing by a processor node.
While considerable emphasis has been placed herein on the various components of the preferred embodiment, it will be appreciated that many alterations can be made and that many modifications can be made in the preferred embodiment without departing from the principles of the invention. These and other changes in the preferred embodiment as well as other

embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.

We Claim:
1. A system for sending messages and for clash free decoding of Lower Density Parity Check (LDPC) codes, between a set of variable node elements and a set of check node elements, for a set of interconnected processing node elements with a fixed interconnect architecture, said system comprising:
- code generation means adapted to provide LDPC codes;
- Perfect Difference Network (PDN) building means adapted to build Perfect Difference Networks in order to provide said fixed interconnect architecture;
- first mapping means adapted" to map said LDPC code on a built PDN having node elements of pre-fixed size;
- second mapping means adapted to map factor graph based signal processing algorithms on said built PDN for facilitating reusability of said interconnected processing node elements; and
- sum-product algorithm based iterative decoding means adapted to iteratively decode said messages by providing a soft decision message passing algorithm means to accept the probability of each received bit as input.
2. A system as claimed in claim 1 wherein, said Perfect Difference Network building means includes means to build Perfect Difference Networks based on Perfect Difference Sets.

3. A system as claimed in claim 1 wherein, said Perfect Difference Network building means includes means to build Perfect Difference Networks based on 2-dimensional Projective Geometry constructs over prime elements.
4. A system as claimed in claim 1 wherein, said sum-product algorithm based iterative decoding means includes Log Likelihood Ratio generation means adapted to generate probability values for decoding as Log Likelihood Ratio values.
5. A system as claimed in claim 1 wherein, said sum-product algorithm based iterative decoding means includes initialization means adapted to provide an initialisation Log Likelihood Ratio value based on communication channel used for said system.
6. A system as claimed in claim 1 wherein, said system includes iteration limiting means adapted to provide limits for said iterative decoding means.
7. A system as claimed in claim 1 wherein, said sum-product algorithm based iterative decoding means includes iteration limiting means adapted to provide limits for iterative decoding means and further includes iteration means adapted to iteratively pass said messages between said set of variable

node elements and said set of check node elements until said iterative limit is valid.