Signal-flow graph

Summary

A signal-flow graph or signal-flowgraph (SFG), invented by Claude Shannon, but often called a Mason graph after Samuel Jefferson Mason who coined the term, is a specialized flow graph, a directed graph in which nodes represent system variables, and branches (edges, arcs, or arrows) represent functional connections between pairs of nodes. Thus, signal-flow graph theory builds on that of directed graphs (also called digraphs), which includes as well that of oriented graphs. This mathematical theory of digraphs exists, of course, quite apart from its applications. SFGs are most commonly used to represent signal flow in a physical system and its controller(s), forming a cyber-physical system. Among their other uses are the representation of signal flow in various electronic networks and amplifiers, digital filters, state-variable filters and some other types of analog filters. In nearly all literature, a signal-flow graph is associated with a set o

Official source

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Related people

Related units

Related concepts

Related courses

Related lectures

Distributed graph signal processing algorithms require the network nodes to communicate by exchanging messages in order to achieve a common objective. These messages have a finite precision in realistic networks, which may necessitate to implement message quantization. Quantization, in turn, may generate distortion and performance penalty in the distributed processing tasks. This paper proposes a novel method for distributed graph filtering that minimizes the error due to message quantization without compromising the communication costs. It first bounds the exchanged messages and then allocates a limited bit budget in an optimized way to the different messages and network nodes. In particular, our novel quantization algorithm adapts to both the network topology and the message importance in a distributed processing task. Our results show that the proposed method is effective in minimizing the error due to quantization and that it permits to outperform baseline distributed algorithms when the bit budget is limited. They further show that errors produced in nodes with high eccentricity or in the first steps of the distributed algorithm contribute more to the global error. Also, sparse and irregular graphs require more irregular bit distribution. Our method provides one of the first quantization solutions for distributed graph processing, which is able to adapt to the target task, the graph properties and the communication constraints.

2019

Optimized Quantization in Distributed Graph Signal Processing

Isabela Cunha Maia Nobre, Pascal Frossard

Distributed graph signal processing methods require that the graph nodes communicate by exchanging messages. These messages have a finite precision in a realistic network, which may necessitate to implement quantization. Quantization, in turn, generates errors in the distributed processing tasks, com- pared to perfect settings. This paper proposes a novel method to minimize the quantization error without compromising the communication costs by bounding the exchanged messages along with allocating a limited bit budget through the network in an optimized way. In particular, the quantization adapts to the network topology and message importance in the iterative distributed processing algorithm. Our results show that the proposed method is efficient in minimizing the quantization error and that it outperforms baseline algorithms when the bit budget is limited.

IEEE2019

Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison

David Shuman

A major line of work in graph signal processing [2] during the past 10 years has been to design new transform methods that account for the underlying graph structure to identify and exploit structure in data residing on a connected, weighted, undirected graph. The most common approach is to construct a dictionary of atoms (building block signals) and represent the graph signal of interest as a linear combination of these atoms. Such representations enable visual analysis of data, statistical analysis of data, and data compression, and they can also be leveraged as regularizers in machine learning and ill-posed inverse problems, such as inpainting, denoising, and classification.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020