Before we formally introduce this, we require the notion of computation tree and introduce some more notations. Definition 1: [16] A computation tree corresponding to a message-passing decoder of the Tanner graph G is a tree that is constructed by choosing an arbitrary variable node in G as its root and then recursively adding edges and leaf nodes to the tree that correspond to the messages passed in the decoder up to a certain number of iterations. For each vertex that is added to the tree, the corresponding node update function in G is also copied. H . The isolation assumption is satisfied for two iterations if none of the descendants of the check nodes c$_{7}$ and c$_{8}$ appear as a descendant of check node c$_{9}$ (similar condition has to hold for c$_{10}$ ), and if the only common descendants of the degree-2 check nodes are nodes in H . But the independence assumption does not hold for two iterations. Theorem 1 (Isolation theorem): Let G = { V ∪ C,E } of a 3-left-regular code which contains a subgraph H = { P ∪ W,E $^{′}$} that is induced by a trapping set ( a,b ) . Let W ′ ⊆ W denote the set of degree-one check nodes in H and let P ′ ⊆ P denote the set of variable nodes in H where each has at least one neighbor in W $^{′}$. If r is input to decoder F from the BSC such that supp ( r ) ∈ P , and if H satisfies the isolation assumption in G for k iterations, then for each c$_{j}$ ∈ W $^{′}$, the message from c$_{j}$ to its neighbor in H in the l th iteration denoted by µ$_{l}$ , is determined as the output of Φ$_{v}$( µ$_{l}$$_{−}$$_{1}$,µ$_{l}$$_{−}$$_{1}$, C) ∀ l ≤ k . Remark: Note that the isolation assumption and theorem can be restated for the min-sum decoder. Corollary 1: Consider the min-sum decoder for 3-left- regular LDPC codes with Y = {± 1 } . If subgraph H contained in G satisfies the isolation assumption for k iterations, and if all variable nodes outside H are initially correct, then µ$_{l}$ of the degree-one check node for the min-sum decoder is 2 µ$_{l}$$_{−}$$_{1}$ + 1 . Corollary 2: If H is a subgraph contained in G such that it satisfies the isolation assumption for k iterations, and if all variable nodes outside H are initially correct, then the computation tree T k i ( G ) with v$_{i}$ ∈ P is equivalent to T k i ( H ) , provided µ$_{l}$ for each degree-one check node in H is computed Proof: This follows by looking at the computation tree T l i ( G ) where l ≤ k with any v$_{i}$ ∈ P ′ as its root. Let the initial messages passed from a variable node be ± µ$_{0}$ ∈ M . Since supp ( r ) ∈ P , due to the isolation assumption, this means that all the variable nodes that are descendants to any c$_{j}$ ∈ W ′ are initially correct. In the initial iteration, from the definition of Φ$_{c}$ , the outgoing message of check nodes that are descendants to c$_{j}$ is µ$_{0}$ . In the next iteration, the variable nodes connected to these check nodes receive µ$_{0}$ on all their edges due to the isolation assumption and send Φ$_{v}$( µ$_{0}$,µ$_{0}$, C) as their outgoing messages. Due to the definition of Φ$_{c}$ , the check nodes connected to these nodes in T l i ( G ) send µ$_{1}$ which is simply Φ$_{v}$( µ$_{0}$,µ$_{0}$, C) . This process inductively follows while traversing up the tree for l iterations. Moreover, computation of the hard-decision value for any node v$_{i}$ in H requires only messages from nodes in H in addition to µ$_{l}$ . Let G be the Tanner graph of a 3-left-regular code. Let H be the induced subgraph of a trapping set ( a,b ) contained in G with variable node set P ⊆ V and check node set W ⊆ C . Let N ( u ) denote the set of neighbors of a node u . Let T k i ( G ) be the computation tree of graph G corresponding to a decoder F enumerated for k iterations with variable node v$_{i}$ ∈ V as its root. Let W ′ ⊆ W denote the set of degree-one check nodes in the subgraph H . Let P ′ ⊆ P denote the set of variable nodes in H where each variable node has at least one neighbor in W $^{′}$. During decoding on G , for a node v$_{i}$ ∈ P $^{′}$, let µ$_{l}$ denote the message that v$_{i}$ receives from its neighboring degree-one check node in H in the l th iteration. Definition 2: A vertex w ∈ T k i ( G ) is said to be a descen- dant of a vertex u ∈ T k i ( G ) if there exists a path starting from vertex w to the root v$_{i}$ that traverses through vertex u . The set of all descendants of the vertex u in T k i ( G ) is denoted as D ( u ) . For a given vertex set U , D ( U ) (with some abuse of notation) denotes the set of descendants of all u ∈ U . Definition 3: T k i ( H ) is called the computation tree of the subgraph H enumerated for k iterations for the decoder F , if ∀ c$_{j}$ ∈ W $^{′}$, µ$_{l}$ is given for all l ≤ k , and if the root node v$_{i}$ ∈ P requires only the messages computed by the nodes in H and µ$_{l}$ to compute its binary hard-decision value. Definition 4 (Isolation assumption): The computation tree T k i ( G ) with the root v$_{i}$ ∈ P is said to be isolated if: (i) for any check node c$_{j}$ ∈ W ′ that is in T k i ( G ) with v$_{t}$ ∈ P ′ as its parent, D ( c$_{j}$ ) ∩ D ( N ( v$_{t}$ ) \ c$_{j}$ ) =  , and (ii) for any two check nodes c$_{r}$,c$_{s}$ ∈ W \ W ′ that are also in T k i ( G ) , D ( c$_{r}$ ) ∩ D ( c$_{s}$ ) ⊆ ( P ∪ W ) . If T k i ( G ) is isolated ∀ v$_{i}$ ∈ P , then the subgraph H is said to satisfy the isolation assumption in G for k iterations. Remark: The isolation assumption can still be satisfied even when there are nodes in H that appear multiple times in T k i ( G ) as long as these nodes are not descendants of the degree-one check nodes. Whereas Gallager’s independence assumption will be violated if any node in H is repeated in T k i ( G ) . Hence, isolation assumption is a weaker condition than independence. For clarity, we illustrate with an example shown in Fig. 1. Example 1: Let us assume that the graph G of code C contains a subgraph H induced by a (6 , 2) trapping set. Fig. 1 shows the subgraph H , and the computation tree T 2 3 ( G ) of graph G with v$_{3}$ as its root enumerated for two iterations. The ■ denotes a odd-degree check node. The solid lines represent connections within subgraph H and the dotted lines represent connections from the rest of the graph G outside the subgraph Fig. 1. Subgraph H induced by (6,2) trapping set contained in G : (a) Tanner graph of H ; (b) computational tree T 2 3 ( G ) v$_{1}$ v$_{2}$ v$_{3}$ v$_{4}$ v$_{5}$ v$_{6}$ c$_{1}$ c$_{2}$ c$_{3}$ c$_{4}$ c$_{5}$ c$_{6}$ c$_{10}$ c$_{8}$ c$_{9}$ c$_{7}$ (a) v$_{3}$ c$_{8}$ c$_{9}$ v$_{4}$ v$_{5}$ c$_{7}$ c$_{4}$ c$_{1}$ c$_{2}$ c$_{5}$ v$_{2}$ v$_{1}$ v$_{1}$ v$_{2}$ (b)