Optimal Partitioning Algorithms (OPA) for Discrete Beamforming for Reconfigurable Intelligent Surfaces (RIS)

Authors

Uday Khankhoje, Radha Krishna Ganti, and Sai Sanjay Narayanan

Department of Electrical Engineering Indian Institute of Technology Madras

Contact: uday@ee.iitm.ac.in

Overview

This repository contains MATLAB implementations of optimal partitioning algorithms for computing discrete reflection weights for Intelligent Reflecting Surfaces (IRS) / Reconfigurable Intelligent Surfaces (RIS), as described in our reference paper. These algorithms enable efficient beamforming with discrete phase constraints, addressing the challenge of optimally configuring IRS elements when they can only take on a finite set of reflection coefficients.

The algorithms solve the problem of maximizing the reflected beam intensity (characterized via the array factor) in desired directions while respecting hardware constraints on the available reflection phases at each IRS element. The methods are based on geometric partitioning approaches that efficiently explore the discrete solution space. The algorithms are provably optimal, which means that they will outperform heurtistic/evolutionary algorithms, in addition to negligible run time (for single beam generation).

Key Features

• Support for 1-bit (binary) and k-bit (multi-level) phase quantization
• Quantize phases need not be ideal; arbitrary amplitudes and phases accepted
• Provably optimal algorithms with linear time complexity
• Single and dual beam forming capabilities
• Optional prephasing support for element-specific constraint sets
• Visualization of radiation patterns

Published Work

The algorithms implemented in this repository are described in detail in:

Optimum Beamforming and Grating Lobe Mitigation for Intelligent Reflecting Surfaces Sai Sanjay Narayanan, Uday K Khankhoje, Radha Krishna Ganti IEEE Transactions on Antennas and Propagation, vol. 72, no. 11, pp. 8540-8553, 2024 DOI: 10.1109/TAP.2024.3463805 URL: https://ieeexplore.ieee.org/document/10694729

Algorithm Descriptions

The provided codes implement the following algorithms from the paper:

• Single (1) beam 1-bit algorithms: Instantiations of Algorithm 3 (generalized OPA, "gOPA")
• k-state algorithms (for k > 2 discrete phases): Instantiations of Algorithm 4 ("kOPA")
• Multiple beam algorithms: Instantiations of Algorithm 5

Note: The provided codes only cover some common use cases. The algorithms in the paper can be instantiated in several other settings not covered in this repository. Users are encouraged to adapt the algorithms for their specific requirements. As an example, all the provided codes assume plane wave incidence. However, if you case requires a different kind of incident field, modify the E variable at the start of each code to provide your custom field; the rest of the code will work fine as-is.

Code Files

1. OPA_1bit_1beam.m

Function signature:

[weight, beam_pattern] = OPA_1bit_1beam(array_size, binary_vals, incident_dir, ...
        desired_dir, cell_spacing, wavelength)

Description: Computes optimal 1-bit reflection weights for a single beam using a uniform binary constraint set across all IRS elements.

Inputs:

• array_size: [M, N] array dimensions for M×N IRS
• binary_vals: [a, b] binary constraint set (e.g., [1, -1])
• incident_dir: [theta_in, phi_in] incident beam direction in degrees
• desired_dir: [theta_ref, phi_ref] desired reflection direction in degrees
• cell_spacing: Inter-element spacing (scalar)
• wavelength: Wavelength of EM wave (same units as cell_spacing)

Outputs:

• weight: M×N matrix of optimal reflection weights
• beam_pattern: Figure handle showing radiation pattern along the φ = phi_ref plane

Algorithm: gOPA (Algorithm 3 from paper)

---

2. OPA_1bitpre_1beam.m

Function signature:

[weight, beam_pattern] = OPA_1bitpre_1beam(array_size, A, B, incident_dir, ...
        desired_dir, cell_spacing, wavelength)

Description: Computes optimal 1-bit reflection weights with prephasing for a single beam, allowing element-specific constraint sets.

Inputs:

• array_size: [M, N] array dimensions for M×N IRS
• A, B: M×N matrices where {A_mn, B_mn} is the constraint set for element (m,n)
• incident_dir: [theta_in, phi_in] incident beam direction in degrees
• desired_dir: [theta_ref, phi_ref] desired reflection direction in degrees
• cell_spacing: Inter-element spacing (scalar)
• wavelength: Wavelength of EM wave (same units as cell_spacing)

Outputs:

• weight: M×N matrix of optimal reflection weights
• beam_pattern: Figure handle showing radiation pattern along the φ = phi_ref plane

Algorithm: gOPA with prephasing (Algorithm 3 from paper)

---

3. OPA_1bitpre_2beam.m

Function signature:

[weight, beam_pattern] = OPA_1bitpre_2beam(array_size, A, B, ...
        incident_dir, desired_dir_1, desired_dir_2, ...
        cell_spacing, wavelength, num_samples, num_iter)

Description: Computes optimal 1-bit reflection weights with prephasing for two simultaneous beams in different directions.

Inputs:

• array_size: [M, N] array dimensions for M×N IRS
• A, B: M×N matrices where {A_mn, B_mn} is the constraint set for element (m,n)
• incident_dir: [theta_in, phi_in] incident beam direction in degrees
• desired_dir_1: [theta_ref_1, phi_ref_1] first desired beam direction in degrees
• desired_dir_2: [theta_ref_2, phi_ref_2] second desired beam direction in degrees
• cell_spacing: Inter-element spacing (scalar)
• wavelength: Wavelength of EM wave (same units as cell_spacing)
• num_samples: Number of alpha samples (recommend ≤ 5)
• num_iter: Number of alpha update iterations (recommend ≤ 5)

Outputs:

• weight: M×N matrix of optimal reflection weights
• beam_pattern: Figure handle showing radiation patterns along both φ planes

Algorithm: Multi-beam algorithm (Algorithm 5 from paper)

---

4. OPA_kbit_1beam.m

Function signature:

[weight, beam_pattern] = OPA_kbit_1beam(array_size, kbits, incident_dir, ...
        desired_dir, cell_spacing, wavelength)

Description: Computes optimal k-bit reflection weights for a single beam with 2^k discrete equispaced phases.

Inputs:

• array_size: [M, N] array dimensions for M×N IRS
• kbits: Number of bits (k) determining 2^k discrete phases
• incident_dir: [theta_in, phi_in] incident beam direction in degrees
• desired_dir: [theta_ref, phi_ref] desired reflection direction in degrees
• cell_spacing: Inter-element spacing (scalar)
• wavelength: Wavelength of EM wave (same units as cell_spacing)

Outputs:

• weight: M×N matrix of optimal reflection weights
• beam_pattern: Figure handle showing radiation pattern along the φ = phi_ref plane

Algorithm: kOPA (Algorithm 4 from paper)

Example: For kbits = 2, the discrete phases are {1, 1j, -1, -1j} (4 equally spaced phases)

---

5. OPA_kbit_2beam.m

Function signature:

[weight, beam_pattern] = OPA_kbit_2beam(array_size, discrete_weights, ...
        incident_dir, desired_dir_1, desired_dir_2, cell_spacing, wavelength,...
        num_samples, num_iter)

Description: Computes optimal k-state reflection weights for two simultaneous beams with arbitrary discrete weight constraints.

Inputs:

• array_size: [M, N] array dimensions for M×N IRS
• discrete_weights: [a1, a2, ..., ak] array of k arbitrary complex weights
• incident_dir: [theta_in, phi_in] incident beam direction in degrees
• desired_dir_1: [theta_ref_1, phi_ref_1] first desired beam direction in degrees
• desired_dir_2: [theta_ref_2, phi_ref_2] second desired beam direction in degrees
• cell_spacing: Inter-element spacing (scalar)
• wavelength: Wavelength of EM wave (same units as cell_spacing)
• num_samples: Number of alpha samples (recommend ≤ 5)
• num_iter: Number of alpha update iterations (recommend ≤ 5)

Outputs:

• weight: M×N matrix of optimal reflection weights
• beam_pattern: Figure handle showing radiation patterns along both φ planes

Algorithm: Multi-beam algorithm with k-ary partitioning (Algorithm 5 from paper)

Note: This function calls kary_algorithm.m as a helper function.

---

6. kary_algorithm.m

Function signature:

[weight] = kary_algorithm(discrete_weights, complex_numbers)

Description: Helper function that implements the k-ary partitioning algorithm for arbitrary discrete constraint sets.

Inputs:

• discrete_weights: Array of k discrete weight values (constraint set)
• complex_numbers: Array of complex numbers to be weighted

Outputs:

• weight: Array of optimal weights maximizing the absolute value of the weighted sum

Note: This function is called internally by OPA_kbit_2beam.m.

Sign Convention

Important: The angle convention used in these codes differs from standard spherical coordinates for the incident beam; refer to the image signconvention.png (below) for clarification.

Convention Summary

For incident direction [theta_in, phi_in] and reflected direction [theta_ref, phi_ref]:

Incident wavevector:

You must take the incident wavevector (i.e. the blue arrow in the figure) and reverse it. Your input [theta_in, phi_in] refer to the angles of this reversed vector (in usual spherical coordiantes). The code defines the incident wave vector like so:

k_in = -[sin(theta_in)cos(phi_in), sin(theta_in)sin(phi_in), cos(theta_in)]

Note the negative sign -- this ensures such that k_in is the incident wavevector in usual spherical coordinates.

Reflected wavevector:

k_r = +[sin(theta_ref)cos(phi_ref), sin(theta_ref)sin(phi_ref), cos(theta_ref)]

The reflected angles follow standard spherical coordinate convention.

Important Notes

• The IRS is positioned on the xy-plane with elements at positions (m·d, n·d, 0)
• $\theta$ must range from -90° to +90°
• $\phi$ ranges from 0° to 360°
• Note that ($\theta$, $\phi$) is equivalent to (-$\theta$, $\phi$+180°)
• Radiation patterns are plotted along the plane $\phi$ = phi_ref

Sample Invocations

This section provides complete examples for each function. First, define common parameters:

% Common parameters for all examples
bvals = [-1, 1];          % Binary weights for 1-bit (k=2)
kvals = [1, 1j, -1, -1j]; % 4 discrete weights for k=4
asize = [10, 15];         % Array size (10×15 IRS)
inc = [-30, 0];           % Incident direction: theta=-30°, phi=0°
de1 = [45, 0];            % First desired beam direction: theta=45°, phi=0°
de2 = [-15, 0];           % Second desired beam direction: theta=-15°, phi=0°
d = 0.25;                 % Inter-element spacing
lam = 1;                  % Wavelength (same units as spacing)
A = ones(asize);          % Prephasing matrix A (all ones)
B = -1 * A;               % Prephasing matrix B (all negative ones)
kbitval = 3;                 % 3-bit weights/element for example 4

Example 1: OPA_1bit_1beam - Single beam, 1-bit, no prephasing

[w, b] = OPA_1bit_1beam(asize, bvals, inc, de1, d, lam);
% Returns:
%   w: 10×15 matrix of optimal binary weights
%   b: Figure handle showing radiation pattern

Example 2: OPA_1bitpre_1beam - Single beam, 1-bit, with prephasing

[w, b] = OPA_1bitpre_1beam(asize, A, B, inc, de1, d, lam);
% Returns:
%   w: 10×15 matrix of optimal weights with element-specific constraints
%   b: Figure handle showing radiation pattern

Example 3: OPA_1bitpre_2beam - Dual beam, 1-bit, with prephasing

[w, b] = OPA_1bitpre_2beam(asize, A, B, inc, de1, de2, d, lam, 4, 4);
% Parameters: 4 samples, 4 iterations for multi-beam algorithm
% Returns:
%   w: 10×15 matrix of optimal weights
%   b: Figure handle showing both radiation patterns

Example 4: OPA_kbit_1beam - Single beam, k-bit (3-bit example)

[w, b] = OPA_kbit_1beam(asize, kbitval, inc, de1, d, lam);
% Uses 2^kbitval states per element 
% Returns:
%   w: 10×15 matrix of optimal weights
%   b: Figure handle showing radiation pattern

Example 5: OPA_kbit_2beam - Dual beam, arbitrary k discrete weights

[w, b] = OPA_kbit_2beam(asize, kvals, inc, de1, de2, d, lam, 3, 3);
% Uses 4 discrete complex weights: [1, 1j, -1, -1j]
% Parameters: 3 samples, 3 iterations for multi-beam algorithm
% Returns:
%   w: 10×15 matrix of optimal weights
%   b: Figure handle showing both radiation patterns

Complete Example with Visualization

% Complete example: 20×20 IRS, 1-bit phases, single beam
% Incident beam from theta=-30°, phi=45°
% Desired beam toward theta=60°, phi=225° (equivalent to theta=-60°, phi=45°)
% Wavelength 5cm, half-wavelength spacing (2.5cm)

array_size = [20, 20];
binary_vals = [1, -1];
incident_dir = [-30, 45];
desired_dir = [60, 225];  % Equivalent to [-60, 45]
cell_spacing = 2.5;       % cm
wavelength = 5.0;         % cm

[weight, beam_pattern] = OPA_1bit_1beam(array_size, binary_vals, ...
    incident_dir, desired_dir, cell_spacing, wavelength);

% The function returns:
%   - weight: 20×20 matrix with optimal reflection coefficients (±1)
%   - beam_pattern: Figure showing the radiation pattern in dB scale

% Display statistics
fprintf('Array dimensions: %d × %d\n', array_size(1), array_size(2));

Requirements

• MATLAB (tested with recent versions)
• No additional toolboxes required

How to Cite

If you use this code in your research, please cite our paper:

BibTeX:

@article{narayanan2024optimum,
  title={Optimum Beamforming and Grating Lobe Mitigation for Intelligent Reflecting Surfaces},
  author={Narayanan, Sai Sanjay and Khankhoje, Uday K and Ganti, Radha Krishna},
  journal={IEEE Transactions on Antennas and Propagation},
  volume={72},
  number={11},
  pages={8540--8553},
  year={2024},
  doi={10.1109/TAP.2024.3463805}
}

Plain text:

Sai Sanjay Narayanan, Uday K Khankhoje, and Radha Krishna Ganti, "Optimum Beamforming and Grating Lobe Mitigation for Intelligent Reflecting Surfaces," IEEE Transactions on Antennas and Propagation, vol. 72, no. 11, pp. 8540-8553, 2024. DOI: 10.1109/TAP.2024.3463805

License

This software is released under the MIT License with explicit exclusion of patent rights. See the LICENSE file for details.

Important: The copyright license does NOT include any patent license. See below for patent information.

Patent Notice

The methods and algorithms implemented in this software are protected by patent:

"Method For Computing Weights For A Beamforming Algorithm From An Intelligent Reflecting Surface"

Inventors: Uday Khankhoje, Radha Krishna Ganti, and Sai Sanjay Narayanan

• US Patent Application No. 19/033,482 (provisional)
• Indian Patent No. 577627 (filed 22.01.2024, granted 07.01.2026)

Usage Rights

• Academic and Research Use: Permitted under the MIT License with attribution
• Commercial Use: Requires a separate patent license

For commercial patent licensing inquiries, please contact: uday@ee.iitm.ac.in

See PATENT_NOTICE file for complete details.

Contributing

We welcome bug reports and suggestions for improvements. Please open an issue on GitHub or contact the authors directly.

Acknowledgments

This research work was conducted at the Indian Institute of Technology Madras.

---

Last updated: January 2026