Bitwise operation | EPFL Graph Search

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor. Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands. On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition. While modern processors usually perform addition and multiplication just as fast as bitwise operations due to their longer instruction pipelines and other architectural design choices, bitwise operations do commonly use less power because of the reduced use of resources. Bitwise operators In the explanations below, any indication of a bit's position is counted from the right (least s

BigDataProcessor2: a free and open-source Fiji plugin for inspection and processing of TB sized image data

Nicolas René Chiaruttini

Modern bioimaging and related areas such as sensor technology have undergone tremendous development over the last few years. As a result, contemporary imaging techniques, particularly electron microscopy (EM) and light sheet microscopy, can frequently generate datasets attaining sizes of several terabytes (TB). As a consequence, even seemingly simple data operations such as cropping, chromatic- and drift-corrections and even visualisation, poses challenges when applied to thousands of time points or tiles. To address this we developed BigDataProcessor2-a Fiji plugin facilitating processing workflows for TB sized image datasets.

OXFORD UNIV PRESS2021

Combinatorial algorithms for wireless information flow

Aurore Amaudruz, Christina Fragouli

A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear binary deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the binary adjacency matrices describing source-destination cuts. However, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes infeasible. In this work, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in binary linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between edges to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-bit processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.

2009

Architecture of a Real-Time Platform Independant GPS L1 Software Receiver

Personal digital assistants or mobile phones applications are not anymore restricted to multimedia or wireless communications, but have been extended to handle Global Positioning System (GPS) functionalities. Consequently, the growing market of GPS capable mobile devices is driving the interest of software receiver solutions as they provide several advantages with respect to traditional hardware implementations. First, they share the same system resources such as the processor, embedded memory and power with other system units, reducing both the size and the costs of their integration. Second, they can be easily reprogrammed – via a firmware update – for incorporating the latest developments, such as the exploitation of the future satellites signals or some improved multipath mitigation techniques. Finally, they offer a more flexible solution for rapid research and development as compared to conventional hardware receivers where the chip design is fixed and obtained after a long integration process. With the increasing performance of modern processors, it becomes now feasible to implement in software a multi-channel GPS receiver operating in real-time. However, a major problem with the software architecture is the large computing resources required for the digital signal processing. Former studies have demonstrated that a straightforward transposition of traditional hardware based architectures into software would lead to an amount of integer operations which is not suitable for today's fastest computers. From this observation, several strategies have been proposed in the literature in order to reduce the complexity of the receiver operations. The first one relies on the utilization of advanced microprocessor instructions set which provides the capability of processing vectors of data by operating on multiple integer values at the same time. This results in significant gains in execution speed, but also severely limits the portability of the code, since the operations are tied to specific processors architectures. Another alternative consists in exploiting the native bitwise representation of the signal. The data bits are stored in separate vectors on which logical parallel operations can be performed. The objective is to take advantage of the universality, high parallelism, and speed of the bitwise operations for which a single integer operation translates into a few simple parallel logical relations. However, the inherent drawback of the bitwise processing is the lack of flexibility as the complexity becomes bit-depth dependent. This thesis has been carried out in the framework of a two-year industrial project (2007-2009) in collaboration with U-blox AG in Thalwil. It aimed to the realization of a multi-channel, platform-independent real-time GPS L1 software receiver. The main challenge of this project consisted in providing real-time performances while keeping the portability of the code to make the receiver suitable for any type of software implementation. In that sense, new techniques and algorithms have been developed for optimizing the processing chain in order to lower the processor load. The main idea consists in regrouping data which share the same characteristics, and process them in batches instead of sequentially. This way, it becomes possible to progressively reduce the data throughput and consequently the amount of operations to perform. A completely new receiver architecture has been proposed and validated through the realization of a functional prototype, thus demonstrating the feasibility of the concept.

EPFL2010

Architecture of a Real-Time Platform Independant GPS L1 Software Receiver

EPFL2010