Related Experiment Video
Updated: Nov 23, 2025
14:05
One Dimensional Turing-Like Handshake Test for Motor Intelligence
Published on: December 15, 2010
28.2K
On the Interactive Capacity of Finite-State Protocols
Assaf Ben-Yishai1, Young-Han Kim2, Rotem Oshman3
1School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem 9190401, Israel.
Entropy (Basel, Switzerland)
|December 30, 2020
Summary
This study determines the interactive capacity for finite-state protocols, showing they can be simulated reliably at the Shannon capacity. This resolves a long-standing challenge in information theory for specific protocol types.
Area of Science:
- Information Theory
- Computer Science
- Communication Systems
Background:
- Interactive capacity quantifies reliable simulation rates over noisy channels.
- Calculating interactive capacity is complex, with known bounds often far from the Shannon capacity.
- Existing upper bounds (Shannon capacity) are generally the best known but not tight for interactive protocols.
Purpose of the Study:
- To determine the interactive capacity for simulating finite-state protocols.
- To investigate if finite-state protocols can achieve the Shannon capacity for reliable simulation.
- To establish tighter bounds for interactive capacity in restricted settings.
Main Methods:
- Analysis of interactive protocols within a restricted finite-state model.
- Theoretical investigation of simulation rates over noisy communication channels.
- Comparison of achievable simulation rates against the Shannon capacity.
Main Results:
- All two-state protocols can be simulated reliably at the Shannon capacity.
- Rich families of arbitrary finite-state protocols also achieve the Shannon capacity.
- The interactive capacity is established for these specific classes of finite-state protocols.
Conclusions:
- The interactive capacity problem is solved for two-state and certain arbitrary finite-state protocols.
- Simulation at Shannon capacity is achievable for these protocols, bridging a gap in information theory.
- This work provides a significant advancement in understanding reliable communication over noisy channels.
More Related Videos
08:36Dynamic Inter-subject Functional Connectivity Reveals Moment-to-Moment Brain Network Configurations Driven by Continuous or Communication Paradigms
Published on: March 21, 2019
7.5K
07:43Author Spotlight: A Novel Setup to Conduct Naturalistic Laboratory Experiments with Real Human Actors in Scenarios
Published on: August 4, 2023
2.5K
Related Concept Videos
01:25Network Function of a Circuit
471
Frequency response analysis in electrical circuits provides vital insights into a circuit's behavior as the frequency of the input signal changes. The transfer function, a mathematical tool, is instrumental in understanding this behavior. It defines the relationship between phasor output and input and comes in four types: voltage gain, current gain, transfer impedance, and transfer admittance. The critical components of the transfer function are the poles and zeros.
471
01:24BIBO stability of continuous and discrete -time systems
756
System stability is a fundamental concept in signal processing, often assessed using convolution. For a system to be considered bounded-input bounded-output (BIBO) stable, any bounded input signal must produce a bounded output signal. A bounded input signal is one where the modulus does not exceed a certain constant at any point in time.
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system....
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system....
756
01:23Transfer Function to State Space
578
State-space representation is a powerful tool for simulating physical systems on digital computers, necessitating the conversion of the transfer function into state-space form. Consider an nth-order linear differential equation with constant coefficients, like those encountered in an RLC circuit. The state variables are selected as the output and its n−1 derivatives. Differentiating these variables and substituting them back into the original equation produces the state equations.
In an RLC...
In an RLC...
578
01:21State Space to Transfer Function
421
The conversion of state-space representation to a transfer function is a fundamental process in system analysis. It provides a method for transitioning from a time-domain description to a frequency-domain representation, which is crucial for simplifying the analysis and design of control systems.
The transformation process begins with the state-space representation, characterized by the state equation and the output equation. These equations are typically represented as:
The transformation process begins with the state-space representation, characterized by the state equation and the output equation. These equations are typically represented as:
421
01:27State Space Representation
375
The frequency-domain technique, commonly used in analyzing and designing feedback control systems, is effective for linear, time-invariant systems. However, it falls short when dealing with nonlinear, time-varying, and multiple-input multiple-output systems. The time-domain or state-space approach addresses these limitations by utilizing state variables to construct simultaneous, first-order differential equations, known as state equations, for an nth-order system.
Consider an RLC circuit, a...
Consider an RLC circuit, a...
375
01:19Cyclic Processes And Isolated Systems
3.2K
A thermodynamic system with zero heat exchange and work is an isolated system. For these systems, the internal energy remains constant.
In the case of a non-isolated system, the change in the internal energy is zero only if the process is cyclic. A thermodynamic process is considered cyclic if the system undergoes a series of changes and returns to its initial state.
Consider a cyclic process that returns to its initial state, undergoing a four-step process. The heat transfer along each...
In the case of a non-isolated system, the change in the internal energy is zero only if the process is cyclic. A thermodynamic process is considered cyclic if the system undergoes a series of changes and returns to its initial state.
Consider a cyclic process that returns to its initial state, undergoing a four-step process. The heat transfer along each...
3.2K