Rhythmbox uses the GStreamer plugin system for media decoding. The plugins that are installed will determine which formats you will be able to play.

By default Fedora 23 includes the necessary plugins for decoding free formats. To search for the packages that support the media you want to play visit GStreamer.

A quick search on our Fedora 23 system reveals which plugins are pre-installed

rpm -qa | grep gstreamer

libnice-gstreamer1-0.1.13-2.fc23.x86_64
PackageKit-gstreamer-plugin-1.0.10-2.fc23.x86_64
gstreamer1-plugins-bad-free-1.6.1-2.fc23.x86_64
gstreamer1-1.6.1-1.fc23.x86_64
gstreamer1-plugins-base-1.6.1-1.fc23.x86_64
gstreamer1-plugins-good-1.6.1-1.fc23.x86_64

Continue reading