Reed-Solomon (RS) codes are commonly used for error correction in multiple applications. Typically, RS codes and their decoding algorithms are defined over finite fields. However, as it has been already stated in the 1980s, their construction can also be described over the complex field. With the increased interest in Compressed Sensing (CS), complex-valued RS codes regained more attention. For implementation, RS codes over the complex field suffer from the computational difficulties arising from finite precision of floating point numbers and degradation caused by noise. Additionally, modern power-decoding based decoding algorithms have not been investigated over the complex field yet. The objective of this thesis is to implement and analyze recent power-decoding based decoding algorithms for complex-valued RS codes which are numerically stable. The connection to CS should be presented as well. The performance of these decoding algorithms and their suitability for CS should be evaluated by numerical simulations.