# US 2023/0144556 A1 · Fpga implementation device and method for fblms algorithm based on block floating point

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0144556 A1
- Document ID: US20230144556A1
- Status: Published application
- Kind: A1
- Application number: 17/917,643
- Filed: 2020-05-25
- Published: 2023-05-11
- Earliest claimed: 2020-04-13
- Assignees: Institute of Automation, Chinese Academy of Sciences; Guangdong Institute of Artificial Intelligence and Advanced Computing
- Applicants: Institute of Automation, Chinese Academy of Sciences; Guangdong Institute of Artificial Intelligence and Advanced Computing
- Inventors: Lingtian ZHAO; Jie HAO; Jun LIANG; Yafang SONG; Lin SHU; Sai MA; Qiuxiang FAN; Hui FENG
- Web page: https://patentgrep.com/patent/US20230144556A1

## CPC

- G06F 7/4876: {Multiplying}
- G06F 30/34: for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
- G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm}
- H03H 2021/0058: {Block LMS, i.e. in frequency domain}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03H: IMPEDANCE NETWORKS, e.g. RESONANT CIRCUITS; RESONATORS (waveguides, resonators, lines or other devices of the waveguide type H01P)

## Abstract

Disclosed in the present disclosure is an FPGA implementation device and method for an FBLMS algorithm based on block floating point. The method includes: blocking, caching, and reassembling a reference signal, by an input caching and converting module, converting into a block floating point system and performing FFT; filtering, by a filtering module, in a frequency domain and performing dynamic truncation; caching, by an error calculating and output caching module, a target signal on a block basis, converting into a block floating point system, subtracting an output result output from the filtering module from the converted target signal to obtain an error signal, converting the error signal into a fixed point system to obtain a final cancellation result; obtaining, by a weight adjustment amount calculating module and a weight updating and storing module, an adjustment amount of a frequency domain block weight and updating the frequency domain block weight.

## Claims

### Claim 1

An FPGA implementation device for an FBLMS algorithm based on block floating point, comprising an input caching and converting module, a filtering module, an error calculating and output caching module, a weight adjustment amount calculating module and a weight updating and storing module, in which
the input caching and converting module is suitable for blocking, caching, and reassembling an input time domain reference signal according to an overlap-save method, converting the blocked, cached and reassembled signal from a fixed point system to a block floating point system, and then performing fast Fourier transform (FFT) and caching mantissa, to obtain a frequency domain reference signal with a block floating point system, and outputting the frequency domain reference signal with block floating point system to the filtering module and the weight adjustment amount calculating module;
the filtering module is suitable for performing complex multiplication on the frequency domain reference signal with block floating point system and a frequency domain block weight sent by the weight updating and storing module to obtain a complex multiplication result, determining a significant bit according to a maximum absolute value in the complex multiplication result, and then performing dynamic truncation to obtain a filtered frequency domain reference signal, and sending the filtered frequency domain reference signal to the error calculating and output caching module;
the error calculating and output caching module is configured to perform inverse fast Fourier transform (IFFT) on the filtered frequency domain reference signal; the error calculating and output caching module is further configured to perform ping pong cache on an input target signal and convert the cached target signal to a block floating point system; the error calculating and output caching module is further configured to calculate a difference between the target signal converted to block floating point system and the reference signal on which IFFT is performed to obtain an error signal; and the error calculating and output caching module is further configured to divide the error signal into two same signals, where one of which is sent to the weight adjustment amount calculating module, and the other is converted to fixed point system, and then is subjected to cyclic caching, to obtain output continuously cancellation result signals;
the weight adjustment amount calculating module is configured to obtain an adjustment amount of frequency domain block weight with block floating point system based on the error signal and the frequency domain reference signal with block floating point system; and
the weight updating and storing module is configured to convert the adjustment amount of frequency domain block weight with block floating point system to an extended bit width fixed point system, and then updates and stores the updated frequency domain block weight on a block basis; and the weight updating and storing module is further configured to perform dynamic truncation on the updated frequency domain block weight, and then convert a dynamic truncation result to block floating point system, and send the dynamic truncation result to the filtering module.

### Claim 2 (depends on 1)

The device of claim 1, wherein the input caching and converting module comprises a RAM1, a RAM2, a RAM3, a reassembling module, a converting module 1, an FFT module 1 and a RAM4;
the RAM1, RAM2 and RAM3 are configured to divide the input time domain reference signal into data blocks with a length of N by means of cyclic caching;
the reassembling module is configured to reassemble the data blocks with the length of N according to the overlap-save method to obtain an input reference signal with a block length of L point(s); where L=N+M−1 and M is an order of a filter;
the converting module 1 is configured to convert the input reference signal with the block length of L point(s) from fixed point system to block floating point system, and send the converted input reference signal to the FFT module 1;
the FFT module 1 is configured to perform FFT conversion on the data sent by the converting module 1 to obtain a frequency domain reference signal with block floating point system; and
the RAM4 is configured to cache a mantissa of the frequency domain reference signal with block floating point system.

### Claim 3 (depends on 2)

The device of claim 2, wherein the blocking, caching and reassemble the input time domain reference signal according to the overlap-save method comprises:
step F10, storing K data in the input time domain reference signal to an end of AM1 successively; where K=M−1 and M is the order of the filter;
step F20, storing a first batch of N data subsequent to the K data to RAM2 successively;
step F30, storing a second batch of N data subsequent to the first batch of N data to RAM3 successively, and taking the K data at the end of RAM1 and N data in RAM2 as an input reference signal with block length of L point(s), where L=K+N;
step F40, storing a third batch of N data subsequent to the second batch of N data to RAM1 successively, and taking the K data at an end of RAM2 and N data in RAM3 as the input reference signal with block length of L point(s);
step F50, storing a fourth batch of N data subsequent to the third batch of N data to RAM2 successively, and taking the K data at an end of RAM3 and N data in RAM1 as the input reference signal with block length of L point(s); and
step F60, turning to step F30 and repeating step F30 to step F60 until all data in the input time domain reference signal is processed.

### Claim 4 (depends on 1)

The device of claim 1, wherein the filtering module comprises a complex multiplication module 1, a RAMS and a dynamic truncation module 1 in which,
the complex multiplication module 1 is configured to perform complex multiplication on the frequency domain reference signal with block floating point system and the frequency domain block weight sent by the weight updating and storing module to obtain a complex multiplication result;
the RAMS is configured to cache a mantissa of a data on which the complex multiplication operation has been performed; and
the dynamic truncation module 1 is suitable for determining a data significant bit according to the maximum absolute value in the complex multiplication result, and then performing dynamic truncation to obtain the filtered frequency domain reference signal.

### Claim 5 (depends on 4)

The device of claim 4, wherein the determining the data significant bit according to the maximum absolute value in the complex multiplication result, and then performing dynamic truncation comprises:
step G10: obtaining a data of the maximum absolute value in the complex multiplication result;
step G20, detecting from the highest bit of the data of the maximum absolute value, and searching for an earliest bit that is not 0;
step G30, the earliest bit that is not 0 is an earliest significant data bit, and a bit immediately subsequent to the earliest significant data bit is a sign bit; and
step G40, truncating a mantissa of data by taking the sign bit as a start position of truncation, and adjusting a block index to obtain the filtered frequency domain reference signal.

### Claim 6 (depends on 1)

The device of claim 1, wherein the error calculating and output caching module comprises an IFFT module 1, a deleting module, a RAM6, a RAM7, a converting module 2, a difference operation module, a converting module 3, a RAMS, a RAMS and a RAM10, in which:
the IFFT module 1 is configured to perform IFFT on the filtered frequency domain reference signal,
the deleting module is configured to delete a firstM−1 data of a data block on which IFFT has been performed to obtain a reference signal with a block length of N point(s) where M is an order of the filter,
the RAM6 and RAM7 are configured to perform ping-pong cache on the input target signal to obtain a target signal with a block length of N point(s),
the converting module 2 is configured to convert the target signal with the block length of N point(s) to block floating point system on a block basis;
the difference operation module is configured to calculate a difference between the target signal converted to block floating point system and the reference signal with block length of N point(s) to obtain an error signal; and divide the error signal into two same signals and send the two same signals to the weight adjustment amount calculating module and the converting module 3, respectively,
the converting module 3 is configured to convert the error signal to fixed point system; and
the RAMS, RAM9 and RAM10 are configured to convert the error signal with fixed point system to output continuously cancellation result signals by means of cyclic caching.

### Claim 7 (depends on 1)

The device of claim 1, wherein the weight adjustment amount calculating module comprises a conjugate module, a zero inserting module, an FFT module 2, a complex multiplication module 2, a RAM11, a dynamic truncation module 2, an IFFT module 2, a zero setting module, an FFT transformation module 3 and a product module in which:
the conjugate module is configured to perform conjugation operation on the frequency domain reference signal with block floating point system output from the input caching and converting module,
the zero inserting module is configured to insert M−1 zeros at the front end of the error signal where M is an order of the filter,
the FFT module 2 is configured to perform FFT conversion on the error signal into which zeroes are inserted,
the complex multiplication module 2 is configured to perform complex multiplication on the data on which the conjugation operation is performed and the data on which FFT is performed to obtain a complex multiplication result,
the RAM11 is configured to cache a mantissa of the complex multiplication result,
the dynamic truncation module 2 is configured to determine a data significant bit according to the maximum absolute value in the complex multiplication result of the multiplication module 2, and then perform dynamic truncation to obtain an update amount of the frequency domain block weight,
the IFFT module 2 is configured to perform IFFT on the update amount of the frequency domain block weight,
the zero setting module is configured to set L-M data point(s) at a rear end of the data block on which the IFFT is performed by the IFFT module 2 to 0,
the FFT module 3 is configured to preform FFT on the data output from the zero setting module; and
the product module is configured to perform product operation between the data on which FFT is performed by the FFT transformation module 3 and a set step factor to obtain an adjustment amount of the frequency domain block weight with block floating point system.

### Claim 8 (depends on 1)

The device of claim 1, wherein the weight updating and storing module comprises a converting module 4, a summing operation module, a RAM12, a dynamic truncation module 3 and a converting module 5 in which:
the converting module 4 is configured to convert the adjustment amount of the frequency domain block weight with block floating point system output from the weight adjustment amount calculating module to the extended bit width fixed point system;
the summing operation module is configured to sum the adjustment amount of the frequency domain block weight with extended bit width fixed point system and a stored original frequency domain block weight to obtain an updated frequency domain block weight;
the RAM12 is configured to cache the updated frequency domain block weight;
the dynamic truncation module 3 is configured to determine a data significant bit according to the maximum absolute value in the cached updated frequency domain block weight, and then perform dynamic truncation; and
the converting module 5 is configured to convert the data output from the dynamic truncation module 3 to block floating point system to obtain a frequency domain block weight required by the filtering module.

### Claim 9 (depends on 1)

An FPGA implementation method for FBLMS algorithm based on block floating point, which is based on the FPGA implementation device for FBLMS algorithm based on block floating point of claim 1, the method comprises:
step S10, blocking, caching and reassembling an input time domain reference signal x(n) according to an overlap-save method, converting blocked, cached and reassembled signal from a fixed point system to a block floating point system and performing fast Fourier transform (FFT) to obtain X(k),
step S20, multiplying X(k) by a current frequency domain block weight W(k) to obtain a multiplication result, determining a significant bit according to a maximum absolute value in the multiplication result, and then performing dynamic truncation to obtain a filtered frequency domain reference signal Y(k),
step S30, performing inverse fast Fourier transform (IFFT) on Y(k) and discarding points to obtain a time domain filter output y(k), caching a target signal d(n) on a block basis and converting the cached target signal d(n) to block floating point system to obtain d(k), and subtracting y(k) from d(k) to obtain an error signal e(k), and
step S40, converting the error signal e(k) to fixed point system, then caching and outputting to obtain a final cancellation result signal e(n) output continuously.

### Claim 10 (depends on 9)

The method of claim 9, wherein the frequency domain block weight W(k) is adjusted, calculated and updated synchronously with the error signal e(k) and X(k) by the following steps:
step X10, inserting zero block in e(k) and then performing FFT to obtain the frequency domain error E(k);
step X20, calculating a conjugation of X(k) and multiplying by E(k), and then multiplying by a set step factor ,u to obtain an adjustment amount ΔW(k) of a frequency domain block weight;
step x30, converting ΔW(k) to extended bit width fixed point system and summing the extended ΔW(k) with the current frequency domain block weight W(k) to obtain an updated frequency domain block weight W(k+1);
step X40, determining a significant bit during storage of the updated frequency domain block weight W(k+1) when the updated frequency domain block weight W(k+1) is stored, and performing a dynamic truncation the updated frequency domain block weight W(k+1) when being output to obtain a dynamic truncation result and converting the dynamic truncation result to block floating point system, to be used as a frequency domain block weight for a next stage.