Lookup table

In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v with key k, a hash table would store the value v in the slot h(k) where h is a hash function i.e. k is used to compute the slot, while in the case of LUT, the value v is stored in slot k, thus directly addressable. The savings in processing time can be significant, because retrieving a value from memory is often faster than carrying out an "expensive" computation or input/output operation. The tables may be precalculated and stored in static program storage, calculated (or "pre-fetched") as part of a program's initialization phase (memoization), or even stored in hardware in application-specific platforms. Lookup tables are also used extensive

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 (25)

Related publications

Related people (3)

Related people

Related units (5)

Related units

Related concepts (27)

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

C (pronounced 'siː – like the letter c) is a general-purpose computer programming language. It was created in the 1970s by Dennis Ritchie, and remains very widely used and influential. By design, C's

In computer science, a pointer is an object in many programming languages that stores a memory address. This can be that of another value located in computer memory, or in some cases, that of memory

Related concepts

Related courses (20)

Related courses

Related lectures (27)

Related lectures

TFHE: Fast Fully Homomorphic Encryption Over the Torus

This work describes a fast fully homomorphic encryption scheme over the torus (TFHE) that revisits, generalizes and improves the fully homomorphic encryption (FHE) based on GSW and its ring variants. The simplest FHE schemes consist in bootstrapped binary gates. In this gate bootstrapping mode, we show that the scheme FHEW of Ducas and Micciancio (Eurocrypt, 2015) can be expressed only in terms of external product between a GSW and an LWE ciphertext. As a consequence of this result and of other optimizations, we decrease the running time of their bootstrapping from 690 to 13 ms single core, using 16 MB bootstrapping key instead of 1 GB, and preserving the security parameter. In leveled homomorphic mode, we propose two methods to manipulate packed data, in order to decrease the ciphertext expansion and to optimize the evaluation of lookup tables and arbitrary functions in RingGSW-based homomorphic schemes. We also extend the automata logic, introduced in Gama et al. (Eurocrypt, 2016), to the efficient leveled evaluation of weighted automata, and present a new homomorphic counter called TBSR, that supports all the elementary operations that occur in a multiplication. These improvements speed up the evaluation of most arithmetic functions in a packed leveled mode, with a noise overhead that remains additive. We finally present a new circuit bootstrapping that converts LWE ciphertexts into low-noise RingGSW ciphertexts in just 137 ms, which makes the leveled mode of TFHE composable and which is fast enough to speed up arithmetic functions, compared to the gate bootstrapping approach. Finally, we provide an alternative practical analysis of LWE based schemes, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key, and we propose concrete parameter sets and timing comparison for all our constructions.

SPRINGER2020

Compressed look-up-table based real-time rectification hardware

Abdulkadir Akin, Ipek Baz, Luis Manuel Gaemperle, Yusuf Leblebici, Alexandre Schmid

Stereo image rectification is a pre-processing step of disparity estimation intended to remove image distortions and to enable stereo matching along an epipolar line. A real-time disparity estimation system needs to perform real-time rectification which requires solving the models of lens distortions, image translations and rotations. Look-up-table based rectification algorithms allow image rectification without demanding high complexity operations. However, they require an external memory to store large size look-up-tables. In this work, we present an intermediate solution that compresses the rectification information to fit the look-up-table into the onchip memory of a Virtex-5 FPGA. The low-complexity decompression process requires a negligible amount of hardware resources for its real-time implementation. The proposed image rectification hardware consumes 0.28% of the DFF and 0.32% of the LUT resources of the Virtex-5 XCUVP-110T FPGA, it can process 347 frames per second for a 1024×768 pixels image resolution, and it does not need the availability of an external memory.

2013

Enhanced Compressed Look-up-Table Based Real-Time Rectification Hardware

Abdulkadir Akin, Luis Manuel Gaemperle, Yusuf Leblebici, Halima Najibi, Alexandre Schmid

Real-time disparity estimation requires real-time rectification which involves solving the models of lens distortions, image translations and rotations. Low complexity look-up-table based rectification algorithms usually require an external memory to store large look-up-tables. In this chapter, we present an implementation of the look-up-table based approach which compresses the rectification information to fit the look-up-table into the on-chip memory of a Virtex-5 FPGA. First, a very low complexity compressed look-up-table based rectification algorithm (CLUTR) and its real-time hardware are presented. The implemented CLUTR hardware rectifies stereo images with moderate lens distortion and camera misalignment. Moreover, an enhanced version of the compressed look-up-table based rectification algorithm (E-CLUTR) and its novel real-time hardware are presented. E-CLUTR solves more extreme camera alignment and distortion issues than CLUTR while maintaining the low complexity architecture.

Springer-Verlag Berlin2015

In computer science, a pointer is an object in many programming languages that stores a memory address. This can be that of another value located in computer memory, or in some cases, that of memory

MSE-704: 3D Electron Microscopy and FIB-Nanotomography

The principles of 3D surface (SEM) reconstruction and its limitations will be explained. 3D volume reconstruction and tomography methods by electron microscopy (SEM/FIB and TEM) will be explained and compared with x-ray tomography.

EE-208: Microcontrollers and digital systems

Microcontrôleurs et conception de systèmes numériques couvre le fonctionnement interne d'un microcontrôleur, des notions de base d'architecture de processeur et de système informatique ainsi que les interfaces de microcontrôleurs, et protocoles de communication série.

CS-210: Functional programming

Understanding of the principles and applications of functional programming, the fundamental models of program execution, application of fundamental methods of program composition, meta-programming through the construction of interpreters and advanced programming techniques.