Fundamentals of Codes, Graphs, and Iterative Decoding / The Springer International Series in Engineering and Computer Science Bd.714 (PDF)
(Sprache: Englisch)
Fundamentals of Codes, Graphs, and Iterative Decoding is an explanation of how to introduce local connectivity, and how to exploit simple structural descriptions. Chapter 1 provides an overview of Shannon theory and the basic tools of complexity theory,...
sofort als Download lieferbar
eBook (pdf)
Fr. 59.00
inkl. MwSt.
- Kreditkarte, Paypal, Rechnung
- Kostenloser tolino webreader
Produktdetails
Produktinformationen zu „Fundamentals of Codes, Graphs, and Iterative Decoding / The Springer International Series in Engineering and Computer Science Bd.714 (PDF)“
Fundamentals of Codes, Graphs, and Iterative Decoding is an explanation of how to introduce local connectivity, and how to exploit simple structural descriptions. Chapter 1 provides an overview of Shannon theory and the basic tools of complexity theory, communication theory, and bounds on code construction. Chapters 2 - 4 provide an overview of "classical" error control coding, with an introduction to abstract algebra, and block and convolutional codes. Chapters 5 - 9 then proceed to systematically develop the key research results of the 1990s and early 2000s with an introduction to graph theory, followed by chapters on algorithms on graphs, turbo error control, low density parity check codes, and low density generator codes.
Lese-Probe zu „Fundamentals of Codes, Graphs, and Iterative Decoding / The Springer International Series in Engineering and Computer Science Bd.714 (PDF)“
Chapter 5 ELEMENTS OF GRAPH THEORY (p. 79-80)
The graph-theoretic interpretation of error control codes has led to construction techniques for codes whose performance is extremely close to the Shannon limit. The next several chapters discuss these constructions techniques. In this chapter we consider several basic results that will be used throughout the rest of the book.
We begin with a basic definition for graphs, and then proceed to a discussion of the important class of bipartite graphs. A method is presented for transforming a non-bipartite graph into a bipartite graph through the use of edge-vertex incidence graphs. The powerful probabilistic technique of martingales is then introduced as a tool for use in bounding the deviation of a random variable from its expected value. Using this technique, many properties of a graph can be bounded exponentially around their respective expected values. A definition is then given for an expander graph, a graph in which each vertex has a large number of neighbors, where a neighbor is a node to which the first node is directly connected by an edge.
The properties of such graphs will prove useful in that they are natural analogs of codes in which the value of an information bit is spread across several codeword bits. Intuitively, such a situation provides a large number of options for recovering the value of an information bit in the presence of noise. We derive a lower bound on the expansion of a randomly chosen graph.
This result shows that a randomly chosen graph will be an expander with high probability. One important consequence of the proof of this result is that a regular graph is a good expander if and only if the eigenvalue of the graph with the second largest magnitude is well separated from the eigenvalue with the largest magnitude. We provide a lower bound on the second largest eigenvalue of a regular graph and describe an explicit construction for a regular graph that achieves
... mehr
the lower bound. This gives the best explicit expander known.
1. Introduction
We begin with a basic definition for a "graph".
Definition 145 A graph G is an ordered pair (V, E) of a set of vertices V and a set of edges E. An edge is a pair of distinct vertices from V. In a simple example below, the graph consists of the vertex set V = {A, B, C, D, E, F} and the edge set E = {(A, D), (B, D), (C, E), (D, E)}. This particular graph is disconnected in that paths do not exist between arbitrary pairs of vertices in the graph. In this case the vertex F is not connected by an edge to any other vertex. This graph is also undirected in that there is no directionality associated with the edges. In a directed graph, the edges are ordered pairs of vertices, with the first vertex being the originating vertex and the second the terminating vertex.
1. Introduction
We begin with a basic definition for a "graph".
Definition 145 A graph G is an ordered pair (V, E) of a set of vertices V and a set of edges E. An edge is a pair of distinct vertices from V. In a simple example below, the graph consists of the vertex set V = {A, B, C, D, E, F} and the edge set E = {(A, D), (B, D), (C, E), (D, E)}. This particular graph is disconnected in that paths do not exist between arbitrary pairs of vertices in the graph. In this case the vertex F is not connected by an edge to any other vertex. This graph is also undirected in that there is no directionality associated with the edges. In a directed graph, the edges are ordered pairs of vertices, with the first vertex being the originating vertex and the second the terminating vertex.
... weniger
Bibliographische Angaben
- Autoren: Stephen B. Wicker , Saejoon Kim
- 2006, 2002, 224 Seiten, Englisch
- Verlag: Springer, New York
- ISBN-10: 0306477947
- ISBN-13: 9780306477942
- Erscheinungsdatum: 18.04.2006
Abhängig von Bildschirmgrösse und eingestellter Schriftgrösse kann die Seitenzahl auf Ihrem Lesegerät variieren.
eBook Informationen
- Dateiformat: PDF
- Grösse: 10 MB
- Ohne Kopierschutz
- Vorlesefunktion
Sprache:
Englisch
Kommentar zu "Fundamentals of Codes, Graphs, and Iterative Decoding / The Springer International Series in Engineering and Computer Science Bd.714"
0 Gebrauchte Artikel zu „Fundamentals of Codes, Graphs, and Iterative Decoding / The Springer International Series in Engineering and Computer Science Bd.714“
Zustand | Preis | Porto | Zahlung | Verkäufer | Rating |
---|
Schreiben Sie einen Kommentar zu "Fundamentals of Codes, Graphs, and Iterative Decoding / The Springer International Series in Engineering and Computer Science Bd.714".
Kommentar verfassen